Minimum Operations

Given a number N. Find the minimum number of operations required to reach N starting from 0. You have 2 operations available:

  • Double the number
  • Add one to the number


Example 1:

Input:
N = 8
Output: 4
Explanation: 0 + 1 = 1, 1 + 1 = 2,
2 * 2 = 4, 4 * 2 = 8


Example 2:

Input: 
N = 7
Output: 5
Explanation: 0 + 1 = 1, 1 + 1 = 2,
1 + 2 = 3, 3 * 2 = 6, 6 + 1 = 7



method : greedy approach


1)run a while loop from n to 0.

2)if its even no. do n=n/2 and increment counter.

3)if its odd no. do n=n-1 and increment counter.

4)when n=0 the while loop will stop than return the counter.




c++ implementation:

int minOperation(int n)
    {
        int c=0;
            while(n)
            {
                if(n%2==0)
                {
                    n=n/2;
                    c++;
                }
                else
                {
                    n=n-1;
                    c++;
                }
            }
            return c;
            
    }


Time Complexity: O(logn) 
space Complexity: O(1) 


darkmode