C ++中的整数替换

假设我们有一个正整数n，我们可以按照以下步骤进行这些操作-

• 如果n为偶数，则将n替换为n / 2。

• 如果n为奇数，则可以将n替换为n + 1或n-1。

我们必须找到n变为1所需的最小替换数？

因此，如果数字为7，则答案将为4，例如7→8→4→2→1或7→6→3→2→1

为了解决这个问题，我们将遵循以下步骤-

• ret：= 0，n：= x

• 当n> 1时

• 如果n为3或n / 2为偶数，则将n减1，否则将n加1

• 如果n是偶数，则c：= n / 2

• 否则当n为偶数时

• 增加ret 1

• 返回ret。

范例（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int bitCount(int x){
      int ret = 0;
      while(x){
         ret++;
         x >>= 1;
      }
      return ret;
   }
   int integerReplacement(int x) {
      int ret = 0;
      lli n = x;
      while(n > 1){
         if(n % 2 == 0){
            n >>= 1;
         }
         else if(n & 1){
            if(n == 3 || (((n >> 1) & 1 )== 0)){
               n--;
            } else {
               n++;
            }
         }
         ret++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.integerReplacement(7));
}

输入值

7

输出结果

4