Minimizing Operations to Reach N from 0
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
Examples:
Input: N = 8
Output: 4
Explanation: 0 + 1 = 1 –> 1 + 1 = 2 –> 2 * 2 = 4 –> 4 * 2 = 8.Input: N = 7
Output: 5
Explanation: 0 + 1 = 1 –> 1 + 1 = 2 –> 1 + 2 = 3 –> 3 * 2 = 6 –> 6 + 1 = 7.
Approach: To solve the problem follow the below idea:
The idea is to use greedy algorithm. Think this problem in reverse order like, if we have to reduce given number n to 0. Now, we’ll approach in a way that if n is even then divided it by 2 otherwise, decrement it by 1 and keep a count variable to keep track of operation required to do.
Step-by-step approach:
- Keep a variable count for tracking number of operations.
- Loop until given number is positive number.
- Check if number is even, then divide it by 2.
- Otherwise, decrement it by 1.
- Increment the count by 1.
- Return count.
Below is implementation of the above approach:
C++
C++
#include <bits/stdc++.h> using namespace std; // Function to calculate the minimum number // of operations required to make the given // number n equal to 0. The operations allowed // are either dividing n by 2 (if it's // even) or subtracting 1 from n. int minOperation( int n) { int count = 0; while (n > 0) { // If n is even, divide it by 2. if (n % 2 == 0) { n /= 2; } // If n is odd, subtract 1 from it. else { n -= 1; } count++; } return count; } // Drivers code int main() { int n; // Test cases n = 8; // 8 -> 4 -> 2 -> 1 -> 0, so it takes 4 // operations. cout << "Minimum operations for n = " << n << ": " << minOperation(n) << endl; n = 15; // 15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0, so it // takes 7 operations. cout << "Minimum operations for n = " << n << ": " << minOperation(n) << endl; n = 1; // 1 -> 0, so it takes 1 operation. cout << "Minimum operations for n = " << n << ": " << minOperation(n) << std::endl; return 0; } |
Java
public class MinimumOperations { public static int minOperation( int n) { int count = 0 ; while (n > 0 ) { // If n is even, divide it by 2. if (n % 2 == 0 ) { n /= 2 ; } // If n is odd, subtract 1 from it. else { n -= 1 ; } count++; } return count; } public static void main(String[] args) { int n; // Test cases n = 8 ; // 8 -> 4 -> 2 -> 1 -> 0, so it takes 4 operations. System.out.println( "Minimum operations for n = " + n + ": " + minOperation(n)); n = 15 ; // 15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0, so it takes 7 operations. System.out.println( "Minimum operations for n = " + n + ": " + minOperation(n)); n = 1 ; // 1 -> 0, so it takes 1 operation. System.out.println( "Minimum operations for n = " + n + ": " + minOperation(n)); } } |
Python3
def min_operation(n): count = 0 while n > 0 : # If n is even, divide it by 2. if n % 2 = = 0 : n / / = 2 # If n is odd, subtract 1 from it. else : n - = 1 count + = 1 return count # Test cases n = 8 print ( "Minimum operations for n =" , n, ":" , min_operation(n)) n = 15 print ( "Minimum operations for n =" , n, ":" , min_operation(n)) n = 1 print ( "Minimum operations for n =" , n, ":" , min_operation(n)) |
C#
// C# Code using System; public class MinimumOperations { public static int MinOperation( int n) { int count = 0; while (n > 0) { // If n is even, divide it by 2. if (n % 2 == 0) { n /= 2; } // If n is odd, subtract 1 from it. else { n -= 1; } count++; } return count; } public static void Main( string [] args) { int n; // Test cases n = 8; // 8 -> 4 -> 2 -> 1 -> 0, so it takes 4 operations. Console.WriteLine( "Minimum operations for n = " + n + ": " + MinOperation(n)); n = 15; // 15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0, so it takes 7 operations. Console.WriteLine( "Minimum operations for n = " + n + ": " + MinOperation(n)); n = 1; // 1 -> 0, so it takes 1 operation. Console.WriteLine( "Minimum operations for n = " + n + ": " + MinOperation(n)); } } |
Javascript
// Javascript code class MinimumOperations { static minOperation(n) { let count = 0; while (n > 0) { // If n is even, divide it by 2. if (n % 2 === 0) { n /= 2; } // If n is odd, subtract 1 from it. else { n -= 1; } count++; } return count; } static main() { let n; // Test cases n = 8; // 8 -> 4 -> 2 -> 1 -> 0, so it takes 4 operations. console.log(`Minimum operations for n = ${n}: ${MinimumOperations.minOperation(n)}`); n = 15; // 15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0, so it takes 7 operations. console.log(`Minimum operations for n = ${n}: ${MinimumOperations.minOperation(n)}`); n = 1; // 1 -> 0, so it takes 1 operation. console.log(`Minimum operations for n = ${n}: ${MinimumOperations.minOperation(n)}`); } } // Call the main method MinimumOperations.main(); |
Minimum operations for n = 8: 4 Minimum operations for n = 15: 7 Minimum operations for n = 1: 1
Time Complexity: O(log(n))
Auxiliary Space: O(1)
Contact Us