Given an integer N, the task is to obtain N, starting from 1 using minimum number of operations. The operations that can be performed in one step are as follows:
- Multiply the number by 2.
- Multiply the number by 3.
- Add 1 to the number.
Explanation:
Input: N = 5
Output: 3
Explanation:
Starting value: x = 1
- Multiply x by 2 : x = 2
- Multiply x by 2 : x = 4
- Add 1 to x : x = 5
Therefore, the minimum number of operations required = 3
Input: N = 15
Output: 4
Explanation:
3 operations required to obtain x = 5.
Multiply x by 3 : x = 15.
Therefore, the minimum number of operations required = 4
Approach:
The idea is to use the concept of Dynamic Programming. Follow the steps below:
- If minimum operations to obtain any number smaller than N is known, then minimum operations to obtain N can be calculated.
- Create the following lookup table:
dp[i] = Minimum number of operations to obtain i from 1
- So for any number x, minimum operations required to obtain x can be calculated as:
dp[x] = min(dp[x-1], dp[x/2], dp[x/3])
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to find the minimum number// of operationsint minOperations(int n){ // Storing the minimum operations // to obtain all numbers up to N int dp[n + 1]; // Initial state dp[1] = 0; // Iterate for the remaining numbers for (int i = 2; i <= n; i++) { dp[i] = INT_MAX; // If the number can be obtained // by multiplication by 2 if (i % 2 == 0) { int x = dp[i / 2]; if (x + 1 < dp[i]) { dp[i] = x + 1; } } // If the number can be obtained // by multiplication by 3 if (i % 3 == 0) { int x = dp[i / 3]; if (x + 1 < dp[i]) { dp[i] = x + 1; } } // Obtaining the number by adding 1 int x = dp[i - 1]; if (x + 1 < dp[i]) { dp[i] = x + 1; } } // Return the minm operations // to obtain n return dp[n];}// Driver Codeint main(){ int n = 15; cout << minOperations(n); return 0;} |
Java
class GFG{ // Function to find the minimum number// of operationsstatic int minOperations(int n){ // Storing the minimum operations // to obtain all numbers up to N int dp[] = new int[n + 1]; // Initial state dp[1] = 0; // Iterate for the remaining numbers for(int i = 2; i <= n; i++) { dp[i] = Integer.MAX_VALUE; // If the number can be obtained // by multiplication by 2 if (i % 2 == 0) { int x = dp[i / 2]; if (x + 1 < dp[i]) { dp[i] = x + 1; } } // If the number can be obtained // by multiplication by 3 if (i % 3 == 0) { int x = dp[i / 3]; if (x + 1 < dp[i]) { dp[i] = x + 1; } } // Obtaining the number by adding 1 int x = dp[i - 1]; if (x + 1 < dp[i]) { dp[i] = x + 1; } } // Return the minm operations // to obtain n return dp[n];}// Driver Codepublic static void main (String []args){ int n = 15; System.out.print( minOperations(n));}}// This code is contributed by chitranayal |
Python3
import sys# Function to find the minimum number # of operations def minOperations(n): # Storing the minimum operations # to obtain all numbers up to N dp = [sys.maxsize] * (n + 1) # Initial state dp[1] = 0 # Iterate for the remaining numbers for i in range(2, n + 1): # If the number can be obtained # by multiplication by 2 if i % 2 == 0: x = dp[i // 2] if x + 1 < dp[i]: dp[i] = x + 1 # If the number can be obtained # by multiplication by 3 if i % 3 == 0: x = dp[i // 3] if x + 1 < dp[i]: dp[i] = x + 1 # Obtaining the number by adding 1 x = dp[i - 1] if x + 1 < dp[i]: dp[i] = x + 1 # Return the minimum operations # to obtain n return dp[n]# Driver coden = 15print(minOperations(n)) # This code is contributed by Stuti Pathak |
C#
using System;class GFG{ // Function to find the minimum number// of operationsstatic int minOperations(int n){ // Storing the minimum operations // to obtain all numbers up to N int []dp = new int[n + 1]; int x; // Initial state dp[1] = 0; // Iterate for the remaining numbers for(int i = 2; i <= n; i++) { dp[i] = int.MaxValue; // If the number can be obtained // by multiplication by 2 if (i % 2 == 0) { x = dp[i / 2]; if (x + 1 < dp[i]) { dp[i] = x + 1; } } // If the number can be obtained // by multiplication by 3 if (i % 3 == 0) { x = dp[i / 3]; if (x + 1 < dp[i]) { dp[i] = x + 1; } } // Obtaining the number by adding 1 x = dp[i - 1]; if (x + 1 < dp[i]) { dp[i] = x + 1; } } // Return the minm operations // to obtain n return dp[n];} // Driver Codepublic static void Main (string []args){ int n = 15; Console.Write(minOperations(n));}} // This code is contributed by rock_cool |
Javascript
<script>// Function to find the minimum number// of operationsfunction minOperations(n){ // Storing the minimum operations // to obtain all numbers up to N let dp = new Array(n + 1); // Initial state dp[1] = 0; // Iterate for the remaining numbers for(let i = 2; i <= n; i++) { dp[i] = Number.MAX_VALUE; // If the number can be obtained // by multiplication by 2 if (i % 2 == 0) { let x = dp[parseInt(i / 2, 10)]; if (x + 1 < dp[i]) { dp[i] = x + 1; } } // If the number can be obtained // by multiplication by 3 if (i % 3 == 0) { let x = dp[parseInt(i / 3, 10)]; if (x + 1 < dp[i]) { dp[i] = x + 1; } } // Obtaining the number by adding 1 let x = dp[i - 1]; if (x + 1 < dp[i]) { dp[i] = x + 1; } } // Return the minm operations // to obtain n return dp[n];}// Driver codelet n = 15;document.write(minOperations(n));// This code is contributed by divyesh072019</script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
