Maximize the product of digits by incrementing any digit X times
Given two integers N and X. Find the maximum product of digits of N, such that increment any digit by 1 at most X times ( chosen digit < 9)
Example:
Input: N = 2, X = 2
Output: 4
Explanation:
- First Operation: Increment 2 to 3.
- Second Operation: Increment 3 to 4.
Only a single digit is there. Therefore, the output is 4.
Input: N = 2543, X = 4
Output: 400
Explanation:
- First operation: Choose the first digit and increment it from 2 to 3, N = 3543
- Second operation: Choose the last digit and increment it from 3 to 4, N = 3544
- Third operation: Choose the last digit and increment it from 4 to 5, N = 3545
- Fourth operation: Choose the first digit and increment it from 3 to 4. N = 4545
The final value of N after 4 operations is= 4543, whose digits give the product as 4*5*4*5=400. Which is the maximum possible.
Approach: The problem can be solved based on the following idea:
The problem is based on Greedy logic and observation based. We can use the Greedy approach to maximize the product of digits. For more clarification see the Concept of approach section below.
Concept of approach:
The problem is observation based and can be solved by using Greedy technique. Here the Greedy approach comes that, We should increment that digit of N, Which is currently smallest in all of the digits and that digit must be not equal to 9.
This approach can be implemented by looping N to X times and each iteration increment that digit, Which is currently smallest from all of the digits.
Follow the steps to solve the above idea:
- Store the digit of N in array digits[].
- Sort the digits[].
- If, the first element is not equal to 9, increment the digit by 1.
- Again, sort the digits[] array.
- If the first element is equal to 9, Break the loop.
- After X iterations, Calculate the product of the digits array.
Below is the code to implement the approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function for returning maximum // possible product long long Max_Product( int N, int X) { // dynamic Array to store digits of N vector < int > digits; // Temporary variable to store // value of N int temp = N; // Loop for pushing digits // of N in digits vector while (temp != 0) { digits.push_back(temp % 10); temp = temp / 10; } // Length of integer N int length = digits.size(); cout<<length<< " " ; // Sorting digits sort(digits.begin(),digits.end()); // Looping X times for ( int i = 0; i < X; i++) { // Condition when digits is // equal to 9 and then // breaking the loop if (digits[0] == 9) break ; // Incrementing the smallest // digit of vector digits digits[0] = digits[0] + 1; // Sorting digits at each // iteration sort(digits.begin(),digits.end()); } // Variable to hold product // of digits long long Product = 1; // Loop for calculating product of // digits by iterating digits vector for ( int i = 0; i < length; i++) { Product = Product * digits[i]; } // Returning maximum possible // product return Product; } int main() { // Input value of N and X int N = 2543; int X = 4; // Function call cout<<Max_Product(N, X)<<endl; } |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class NewClass1 { // Driver code public static void main(String[] args) throws java.lang.Exception { // Input value of N and X int N = 2543 ; int X = 4 ; // Function call System.out.println(Max_Product(N, X)); } // Function for returning maximum // possible product static long Max_Product( int N, int X) { // Length of integer N int length = Integer.toString(N).length(); // Array to store digits of N int [] digits = new int [length]; // Temporary variable to store // value of N int temp = N; // Counter variable int counter = 0 ; // Loop for initializing digits // of N in digit[] array while (temp != 0 ) { digits[counter] = temp % 10 ; temp = temp / 10 ; counter++; } // Sorting digits[] Arrays.sort(digits); // Looping X times for ( int i = 0 ; i < X; i++) { // Condition when digits is // equal to 9 and then // breaking the loop if (digits[ 0 ] == 9 ) break ; // Incrementing the smallest // digit of digits[] digits[ 0 ] = digits[ 0 ] + 1 ; // Sorting digits[] at each // iteration Arrays.sort(digits); } // Variable to hold product // of digits long Product = 1 ; // Loop for calculating product of // digits by iterating digits[] for ( int i = 0 ; i < length; i++) { Product = Product * digits[i]; } // Returning maximum possible // product return Product; } } |
Python3
# Python code to implement the approach from typing import List # Function for returning maximum possible product def Max_Product(N: int , X: int ) - > int : # list to store digits of N digits = [] # Temporary variable to store value of N temp = N # Loop for pushing digits of N in digits list while temp ! = 0 : digits.append(temp % 10 ) temp = temp / / 10 # Length of integer N length = len (digits) # Sorting digits digits.sort() # Looping X times for i in range (X): # Condition when digits is equal to 9 and then breaking the loop if digits[ 0 ] = = 9 : break # Incrementing the smallest digit of list digits digits[ 0 ] + = 1 # Sorting digits at each iteration digits.sort() # Variable to hold product of digits Product = 1 # Loop for calculating product of digits by iterating digits list for i in range (length): Product * = digits[i] # Returning maximum possible product return Product if __name__ = = '__main__' : # Input value of N and X N = 2543 X = 4 # Function call print (Max_Product(N, X)) |
C#
// C# code to implement the approach using System; public class GFG { // Function for returning maximum // possible product static long Max_Product( int N, int X) { // Length of integer N int length = N.ToString().Length; // Array to store digits of N int [] digits = new int [length]; // Temporary variable to store // value of N int temp = N; // Counter variable int counter = 0; // Loop for initializing digits // of N in digit[] array while (temp != 0) { digits[counter] = temp % 10; temp = temp / 10; counter++; } // Sorting digits[] Array.Sort(digits); // Looping X times for ( int i = 0; i < X; i++) { // Condition when digits is // equal to 9 and then // breaking the loop if (digits[0] == 9) break ; // Incrementing the smallest // digit of digits[] digits[0] = digits[0] + 1; // Sorting digits[] at each // iteration Array.Sort(digits); } // Variable to hold product // of digits long Product = 1; // Loop for calculating product of // digits by iterating digits[] for ( int i = 0; i < length; i++) { Product = Product * digits[i]; } // Returning maximum possible // product return Product; } static public void Main() { // Code // Input value of N and X int N = 2543; int X = 4; // Function call Console.WriteLine(Max_Product(N, X)); } } // This code is contributed by lokesh |
Javascript
// Javascript code to implement the approach // Function for returning maximum // possible product function Max_Product( N, X) { // dynamic Array to store digits of N let digits= new Array(); // Temporary variable to store // value of N let temp = N; // Loop for pushing digits // of N in digits vector while (temp != 0) { digits.push(temp % 10); temp = Math.floor(temp / 10); } // Length of integer N let length = digits.length; // Sorting digits digits.sort(); // Looping X times for (let i = 0; i < X; i++) { // Condition when digits is // equal to 9 and then // breaking the loop if (digits[0] == 9) break ; // Incrementing the smallest // digit of vector digits digits[0] = digits[0] + 1; // Sorting digits at each // iteration digits.sort(); } // Variable to hold product // of digits let Product = 1; // Loop for calculating product of // digits by iterating digits vector for (let i = 0; i < length; i++) { Product = Product * digits[i]; } // Returning maximum possible // product return Product; } // Input value of N and X let N = 2543; let X = 4; // Function call console.log(Max_Product(N, X)); |
400
Time Complexity: O(X*(Z*log(Z))), Where Z is equal to the number of digits in N.
Auxiliary Space: O(Z)
Related Articles: