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が偶数の場合、c：=n / 2

  • それ以外の場合、nが偶数の場合

    • nが3またはn/2が偶数の場合、nを1減らし、それ以外の場合はnを1増やします

  • 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