Minimize steps to change N to power of 2 by deleting or appending any digit
Given an integer N, the task is to find the minimum number of steps required to change the number N to a perfect power of 2 using the following steps:
- Delete any one digit d from the number.
- Add any digit d at the end of the number N.
Examples:
Input: N = 1092
Output: 2
Explanation:
Following are the steps followed:
- Removing digit 9 from the number N(= 1092) modifies it to 102.
- Adding digit 4 to the end of number N(= 102) modifies it to 1024.
After the above operations, the number N is converted into perfect power of 2 and the number of moves required is 2, which is the minimum. Therefore, print 2.
Input: N = 4444
Output: 3
Approach: The given problem can be solved using the Greedy Approach, the idea is to store all the numbers that are the power of 2 and are less than 1020 and check with each number the minimum steps to convert the given number into a power of 2. Follow the steps below to solve the problem:
- Initialize an array and store all the numbers that are the power of 2 and less than 1020.
- Initialize the answer variable best as length + 1 as the maximum number of steps needed.
- Iterate over the range [0, len) where len is the length of the array using the variable x and perform the following steps:
- Initialize the variable, say position as 0.
- Iterate over the range [0, len) where len is the length of the number using the variable i and if the position is less than len(x) and x[position] is equal to num[i], then increase the value of a position by 1.
- Update the value of best as the minimum of best or len(x) + len(num) – 2*position.
- After performing the above steps, print the value of best as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include<bits/stdc++.h> using namespace std; // Function to find the minimum number of // steps required to reduce N to perfect // power of 2 by performing given steps void findMinimumSteps( int N){ string num = to_string(N); long long c = 1; stack<string>a; // Stores all the perfect power of 2 while ( true ){ if (c > pow (10,20) || c>10) break ; a.push(to_string(c)); c = c * 2; } // Maximum number of steps required long long best = num.length() + 1; // Iterate for each perfect power of 2 while (a.empty() == false ){ string x = a.top(); a.pop(); long long position = 0; // Comparing with all numbers for ( int i=0;i<num.length();i++){ if (position < x.length() && x[position] == num[i]) position += 1; } // Update the minimum number of // steps required best = min(best, ( int )x.length() + ( int )num.length() - 2 * position); } // Print the result cout<<(best-1)<<endl; } // Driver Code int main() { int N = 1092; // Function Call findMinimumSteps(N); } // code is contributed by shinjanpatra |
Java
// Java Program to implement // the above approach import java.util.*; class GFG { // Function to find the minimum number of // steps required to reduce N to perfect // power of 2 by performing given steps static void findMinimumSteps( int N) { String num = String.valueOf(N); int c = 1 ; Stack<String> a = new Stack<>(); // Stores all the perfect power of 2 while ( true ) { if (c > ( int )Math.pow( 10 , 20 )|| c> 10 ) { break ; } a.add(String.valueOf(c)); c = c * 2 ; } // Maximum number of steps required int best = num.length()+ 1 ; // Iterate for each perfect power of 2 String x; int i = 0 ; while (!a.isEmpty()) { x = a.pop(); int position = 0 ; // Comparing with all numbers for (i = 0 ; i < num.length(); i++) { if (position < x.length() && x.charAt(position) == num.charAt(i)) position += 1 ; } // Update the minimum number of // steps required best = ( int ) (Math.min(best, x.length() + num.length() - 2 * position)); } // Print the result System.out.print(best- 1 ); } // Driver Code public static void main(String[] args) { int N = 1092 ; // Function Call findMinimumSteps(N); } } // This code is contributed by Rajput-Ji |
Python3
# Python program for the above approach # Function to find the minimum number of # steps required to reduce N to perfect # power of 2 by performing given steps def findMinimumSteps(N): num = str (N) c = 1 a = [] # Stores all the perfect power of 2 while True : if (c > 10 * * 20 ): break a.append( str (c)) c = c * 2 # Maximum number of steps required best = len (num) + 1 # Iterate for each perfect power of 2 for x in a: position = 0 # Comparing with all numbers for i in range ( len (num)): if position < len (x) and x[position] = = num[i]: position + = 1 # Update the minimum number of # steps required best = min (best, len (x) + len (num) - 2 * position) # Print the result print (best) # Driver Code N = 1092 # Function Call findMinimumSteps(N) |
C#
// C# Program to implement // the above approach using System; using System.Collections; class GFG { // Function to find the minimum number of // steps required to reduce N to perfect // power of 2 by performing given steps static void findMinimumSteps( int N) { string num = N.ToString(); int c = 1; Stack a = new Stack(); // Stores all the perfect power of 2 while ( true ) { if (c > Math.Pow(10, 20)|| c>10 ) { break ; } a.Push(c.ToString()); c = c * 2; } // Maximum number of steps required int best = num.Length+1; // Iterate for each perfect power of 2 string x; int i = 0; while (a.Count!=0) { x = a.Peek().ToString(); a.Pop(); int position = 0; // Comparing with all numbers for (i = 0; i < num.Length; i++) { if (position < x.Length && x[position] == num[i]) position += 1; } // Update the minimum number of // steps required best = Math.Min(best, x.Length + num.Length - 2 * position); } // Print the result Console.Write(best-1); } // Driver Code public static void Main() { int N = 1092; // Function Call findMinimumSteps(N); } } // This code is contributed by Pushpesh Raj |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the minimum number of // steps required to reduce N to perfect // power of 2 by performing given steps function findMinimumSteps(N) { num = N.toString() c = 1 a = [] // Stores all the perfect power of 2 while (1) { if (c > Math.pow(10, 20)) { break ; } a.push(c.toString()) c = c * 2 } // Maximum number of steps required best = num.length + 1 // Iterate for each perfect power of 2 for (x of a) { position = 0 // Comparing with all numbers for (let i = 0; i < num.length; i++) { if (position < x.length && x[position] == num[i]) position += 1 } // Update the minimum number of // steps required best = Math.min(best, x.length + num.length - 2 * position) } // Print the result document.write(best) } // Driver Code let N = 1092 // Function Call findMinimumSteps(N) // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us