Integer Replacement in C++

Suppose we have a positive integer n and we can do these operations as follow −

• If n is even, replace n with n/2.

• If n is odd, you can replace n with either n + 1 or n - 1.

We have to find the minimum number of replacements needed for n to become 1?

So if the number is 7, then the answer will be 4, as 7 → 8 → 4 → 2 → 1 or 7 → 6 → 3 → 2 → 1

To solve this, we will follow these steps −

• ret := 0, n := x

• while n > 1

  • if n is even, then c := n / 2

  • otherwise when n is even

    • if n is 3 or n/2 is even, then decrease n by 1, otherwise increase n by 1

  • increase ret by 1

• return ret.

Example (C++)

Let us see the following implementation to get a better understanding −

 Live Demo

#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)); }

Input

7

Output

4