Generate largest N digit number from 0 in K steps by incrementing X or multiplying by Y
Given integers N, K, X and Y. The task is to find the maximum possible N-digit number in K steps starting from 0. Using the operations given below:
- Increment the value by X, or
- Multiply the value with Y
Examples:
Input: N = 2, K = 5, X = 2, Y = 3
Output: 72
Explanation: Sequence would be {0->2->6->8->24->72}Input: N = 2, K = 10, X = 2, Y = 3
Output: 98
Explanation: Sequence would be
{0 -> 0 -> 0 -> 2 -> 6 -> 8 -> 10 -> 30 -> 32 -> 96 -> 98}.
Notice that the above mentioned sequence 0 is multiplied by 3 two times.
Another possible sequence is
{0 -> 0 -> 2 -> 4 -> 6 -> 8 -> 10 -> 30 -> 32 -> 96 -> 98}.Input: N = 3 and K = 4
Output: -1
Explanation: Not possible to create 3-digit number in 4 steps
Approach: The problem can be solved using the concept of recursion. Follow the steps mentioned below:
- For each recursive step exit the recursive call when:
- If the number of steps taken becomes greater than K, then the recursion must be stopped.
- If the count of digits of current number exceeds N, then there is no need to search on that branch.
- If the current number becomes equal to the maximum N-digit number that may be generated then there is no need for further processing. It will reduce the number extra recursive calls.
- Maximum possible N-digit number that may be generated at any moment is (10N – 1).
- Now Recursively call for the method with current number incremented by X and current step incremented by 1.
- Make another recursive call with current number multiplied by Y and current step incremented by 1.
- Store both the results in a variable.
- At any point of recursion, return the maximum of the two results stored in the variable.
Below is the implementation of the above approach
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function for generating largest // N-digit number in K-steps. int largestNDigitNumber( int N, int currentStep, int K, int X, int Y, int currentValue) { // Further processing is useless // ifcCurrent value already becomes equal // to largest N-digit number that // can be generated if (currentValue == pow (10, N) - 1) return currentValue; // Return 0 steps taken is greater than K // and also if N or K equal to Zero. if (currentStep > K || N < 1 || K < 1) return 0; // currentValue exceeds maxValue, // so there is no need to // keep searching on that branch. if (currentValue >= pow (10, N)) return 0; // Recursive calls int result2 = largestNDigitNumber( N, currentStep + 1, K, X, Y, currentValue + X); int result1 = largestNDigitNumber( N, currentStep + 1, K, X, Y, currentValue * Y); // If both the results are zero // it means maximum is reached. if (result1 == 0 && result2 == 0) return currentValue; // Checking for maximum of the two results. return result1 > result2 ? result1 : result2; } // Driver code int main() { int N = 2, K = 10, X = 2, Y = 3; int largest = largestNDigitNumber( N, 0, K, X, Y, 0); // Checking whether the returned result // is a N-digit number or not. if (largest < pow (10, (N - 1))) { cout << ( "-1" ); } else cout << largest; return 0; } |
Java
// Java code to implement the approach import java.util.*; class GFG { // Function for generating largest // N-digit number in K-steps. static int largestNDigitNumber( int N, int currentStep, int K, int X, int Y, int currentValue) { // Further processing is useless // ifcCurrent value already becomes equal // to largest N-digit number that // can be generated if (currentValue == Math.pow( 10 , N) - 1 ) return currentValue; // Return 0 steps taken is greater than K // and also if N or K equal to Zero. if (currentStep > K || N < 1 || K < 1 ) return 0 ; // currentValue exceeds maxValue, // so there is no need to // keep searching on that branch. if (currentValue >= Math.pow( 10 , N)) return 0 ; // Recursive calls int result2 = largestNDigitNumber( N, currentStep + 1 , K, X, Y, currentValue + X); int result1 = largestNDigitNumber( N, currentStep + 1 , K, X, Y, currentValue * Y); // If both the results are zero // it means maximum is reached. if (result1 == 0 && result2 == 0 ) return currentValue; // Checking for maximum of the two results. return result1 > result2 ? result1 : result2; } // Driver code public static void main(String[] args) { int N = 2 , K = 10 , X = 2 , Y = 3 ; int largest = largestNDigitNumber( N, 0 , K, X, Y, 0 ); // Checking whether the returned result // is a N-digit number or not. if (largest < Math.pow( 10 , (N - 1 ))) { System.out.print( "-1" ); } else System.out.print(largest); } } // This code is contributed by 29AjayKumar |
Python3
# Python code for the above approach # Function for generating largest # N-digit number in K-steps. def largestNDigitNumber(N, currentStep, K, X, Y, currentValue): # Further processing is useless # ifcCurrent value already becomes equal # to largest N-digit number that # can be generated if (currentValue = = 10 * * N - 1 ): return currentValue # Return 0 steps taken is greater than K # and also if N or K equal to Zero. if (currentStep > K or N < 1 or K < 1 ): return 0 # currentValue exceeds maxValue, # so there is no need to # keep searching on that branch. if (currentValue > = 10 * * N): return 0 # Recursive calls result2 = largestNDigitNumber( N, currentStep + 1 , K, X, Y, currentValue + X) result1 = largestNDigitNumber( N, currentStep + 1 , K, X, Y, currentValue * Y) # If both the results are zero # it means maximum is reached. if (result1 = = 0 and result2 = = 0 ): return currentValue # Checking for maximum of the two results. return result1 if result1 > result2 else result2 # Driver code N = 2 K = 10 X = 2 Y = 3 largest = largestNDigitNumber(N, 0 , K, X, Y, 0 ) # Checking whether the returned result # is a N-digit number or not. if (largest < 10 * * (N - 1 )): print ( "-1" ) else : print (largest) # This code is contributed by Saurabh Jaiswal. |
C#
// C# code to implement the approach using System; class GFG { // Function for generating largest // N-digit number in K-steps. static int largestNDigitNumber( int N, int currentStep, int K, int X, int Y, int currentValue) { // Further processing is useless // ifcCurrent value already becomes equal // to largest N-digit number that // can be generated if (currentValue == Math.Pow(10, N) - 1) return currentValue; // Return 0 steps taken is greater than K // and also if N or K equal to Zero. if (currentStep > K || N < 1 || K < 1) return 0; // currentValue exceeds maxValue, // so there is no need to // keep searching on that branch. if (currentValue >= Math.Pow(10, N)) return 0; // Recursive calls int result2 = largestNDigitNumber( N, currentStep + 1, K, X, Y, currentValue + X); int result1 = largestNDigitNumber( N, currentStep + 1, K, X, Y, currentValue * Y); // If both the results are zero // it means maximum is reached. if (result1 == 0 && result2 == 0) return currentValue; // Checking for maximum of the two results. return result1 > result2 ? result1 : result2; } // Driver code public static void Main( string [] args) { int N = 2, K = 10, X = 2, Y = 3; int largest = largestNDigitNumber(N, 0, K, X, Y, 0); // Checking whether the returned result // is a N-digit number or not. if (largest < Math.Pow(10, (N - 1))) { Console.Write( "-1" ); } else Console.Write(largest); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function for generating largest // N-digit number in K-steps. function largestNDigitNumber(N, currentStep, K, X, Y, currentValue) { // Further processing is useless // ifcCurrent value already becomes equal // to largest N-digit number that // can be generated if (currentValue == Math.pow(10, N) - 1) return currentValue; // Return 0 steps taken is greater than K // and also if N or K equal to Zero. if (currentStep > K || N < 1 || K < 1) return 0; // currentValue exceeds maxValue, // so there is no need to // keep searching on that branch. if (currentValue >= Math.pow(10, N)) return 0; // Recursive calls let result2 = largestNDigitNumber( N, currentStep + 1, K, X, Y, currentValue + X); let result1 = largestNDigitNumber( N, currentStep + 1, K, X, Y, currentValue * Y); // If both the results are zero // it means maximum is reached. if (result1 == 0 && result2 == 0) return currentValue; // Checking for maximum of the two results. return result1 > result2 ? result1 : result2; } // Driver code let N = 2, K = 10, X = 2, Y = 3; let largest = largestNDigitNumber( N, 0, K, X, Y, 0); // Checking whether the returned result // is a N-digit number or not. if (largest < Math.pow(10, (N - 1))) { document.write( "-1" ); } else document.write(largest); // This code is contributed by Potta Lokesh </script> |
98
Time Complexity: O(2K)
Auxiliary Space: O(1)
Contact Us