Greedy: Replace the integer to 1 by following given conditions

Problem Statement:

You are given a number, you need to apply below operations:

1. If n is even, then replace n with n/2

2. If n is odd, then replace with either n+1 or n-1.

you need to return minimum number of operations need to make n to 1.

Example:

Input: n = 8

Output: 3

Explanation: 8 -> 4 -> 2 -> 1 

Solution Explanation:

We will solve the problem with the help of greedy approach.

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

If n is odd, then do either +1 or -1.

If the odd number is of 4n+1, then -1 is best

If the odd number is of 4n+3, then +1 is best

For 3, the best option is -1

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

int solution(long n) 
{
    int count = 0;

    while(n != 1) 
    {
        if(n % 2 == 0) 
        {
            n /= 2;
        } 
        else if(n == 3 || (n & 3) == 1) 
        {
            n -= 1;
        } 
        else if((n & 3) == 3) 
        {
            n += 1;
        }

        count++;
    }
    return count;
}


int main() 
{
    int n = 8;
    cout << solution(n);
    return 0;
}

Output

3