C++의 정수 대체

<시간/>

양의 정수 n이 있고 다음과 같이 이러한 작업을 수행할 수 있다고 가정합니다. -

n이 짝수이면 n을 n/2로 바꿉니다.
n이 홀수이면 n을 n + 1 또는 n - 1로 바꿀 수 있습니다.

n이 1이 되는 데 필요한 최소 교체 수를 찾아야 합니까?

따라서 숫자가 7이면 답은 7 → 8 → 4 → 2 → 1 또는 7 → 6 → 3 → 2 → 1과 같이 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ret :=0, n :=x
동안 n> 1
- n이 짝수이면 c :=n / 2
- 그렇지 않으면 n이 짝수일 때
  - n이 3이거나 n/2가 짝수이면 n을 1만큼 감소시키고 그렇지 않으면 n을 1만큼 증가시킵니다.
- ret 1 증가
반환 반환.

예시(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));
}

C++의 정수 대체

예시(C++)

입력

출력