Minimize product of two integers by swapping any number of their digits
Given two N-digit integers X and Y, the task is to minimize the product of X and Y by performing the following operation any number of times where we can choose an integer i such that 1β€ i β€ N and swap ith lowest digits of X and Y.
Examples:
Input : N = 2, X = 13, Y = 22
Output: 276
Explanation: On performing the operation once, with i = 1, we get X = 12 and Y = 23 (swapping the rightmost digits of X and Y). Now X*Y would be 276. It isnβt possible to make X*Y less than 276, hence the answer is 276.Input : N = 8, X = 20220122, Y = 21002300
Output: 54558365
Approach: The idea to solve the above problem is:
Let ai and bi is ith lowest digits of X and Y.
X*Y = ββaibj10i+j, (summations ranges from i = 0 to N β 1 and j = 0 to N β 1)
= β βaibi102i + β β(aibj+ajbi)10i+j
Note that no matter what β βaibi102i remains constant. So, we have to minimize β β(aibj + ajbi)10i+j
If ai β aj and bi β bj have same sign then aibj + ajbi is smaller, else aibi + ajbj is smaller. So, X*Y can be minimized by taking smaller of ai and bi as ai and larger as bi.
The following steps can be used to solve the problem:
- For the sake of simplicity, store both X and Y in strings (say x and y).
- Initialize two variables (say newX and newY) that stores the updated values (after performing the required swaps) of X and Y.
- Iterate through all the digits of x and y.
- In the current iteration, if the current digit of x is greater than that of y, apply the swap operation.
- While iterating, keep updating the values of newX and newY.
- At the end of the iteration, compute the product of newX and newY modulo 998244353 and return it as the answer.
Following is the code based on the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; #define int long long const int MOD = 998244353; // Function to Minimize product of two // integers by swapping any number // of their digits int minProduct( int N, int X, int Y) { // Storing both integers in strings string x = to_string(X); string y = to_string(Y); // Initializing two variables to store // the updated values of X and Y such // that the product is minimized int newX = 0, newY = 0; // Iterating through all the // digits of x and y for ( int i = 0; i < N; ++i) { // If current digit of x is greater // than that of y, we apply // the operation if (x[i] > y[i]) swap(x[i], y[i]); // Update the values of // newX and newY newX = (newX * 10 + (x[i] - '0' )) % MOD; newY = (newY * 10 + (y[i] - '0' )) % MOD; } // Compute the product of newX // and newY modulo MOD int ans = newX * newY % MOD; // Return the product return ans; } // Driver code int32_t main() { int N = 2, X = 13, Y = 22; // Function call int answer = minProduct(N, X, Y); cout << answer; return 0; } |
Java
// Java code for the above approach import java.util.*; class GFG { public static final int MOD = 998244353 ; // Function to Minimize product of two // integers by swapping any number // of their digits public static int minProduct( int N, int X, int Y) { // Storing both integers in strings String x = String.valueOf(X); String y = String.valueOf(Y); // Initializing two variables to store // the updated values of X and Y such // that the product is minimized int newX = 0 , newY = 0 ; // Iterating through all the // digits of x and y for ( int i = 0 ; i < N; ++i) { // If current digit of x is greater // than that of y, we apply // the operation if (x.charAt(i) > y.charAt(i)) { char [] temp = x.toCharArray(); temp[i] = y.charAt(i); y = y.substring( 0 , i) + x.charAt(i) + y.substring(i + 1 ); x = new String(temp); } // Update the values of // newX and newY newX = (newX * 10 + (x.charAt(i) - '0' )) % MOD; newY = (newY * 10 + (y.charAt(i) - '0' )) % MOD; } // Compute the product of newX // and newY modulo MOD int ans = ( int )(( long )newX * newY % MOD); // Return the product return ans; } // Driver code public static void main(String[] args) { int N = 2 , X = 13 , Y = 22 ; // Function call int answer = minProduct(N, X, Y); System.out.println(answer); } } // This code is contributed by prasad264 |
Python3
# Python3 code for the above approach MOD = 998244353 # Function to Minimize product of two # integers by swapping any number # of their digits def minProduct(N, X, Y): # Storing both integers in strings x = str (X) y = str (Y) # Initializing two variables to store # the updated values of X and Y such # that the product is minimized newX = 0 newY = 0 # Iterating through all the # digits of x and y for i in range (N): # If current digit of x is greater # than that of y, we apply # the operation if x[i] > y[i]: x, y = y, x # Update the values of # newX and newY newX = (newX * 10 + int (x[i])) % MOD newY = (newY * 10 + int (y[i])) % MOD # Compute the product of newX # and newY modulo MOD ans = newX * newY % MOD # Return the product return ans # Driver code if __name__ = = '__main__' : N = 2 X = 13 Y = 22 # Function call answer = minProduct(N, X, Y) print (answer) |
C#
// C# code for the above approach using System; public class GFG { const int MOD = 998244353; // Function to Minimize product of two // integers by swapping any number // of their digits public static int MinProduct( int N, int X, int Y) { // Storing both integers in strings string x = X.ToString(); string y = Y.ToString(); // Initializing two variables to store // the updated values of X and Y such // that the product is minimized int newX = 0, newY = 0; // Iterating through all the // digits of x and y for ( int i = 0; i < N; ++i) { // If current digit of x is greater // than that of y, we apply // the operation if (x[i] > y[i]) { char temp = x[i]; x = x.Remove(i, 1).Insert(i, y[i].ToString()); y = y.Remove(i, 1).Insert(i, temp.ToString()); } // Update the values of // newX and newY newX = (newX * 10 + (x[i] - '0' )) % MOD; newY = (newY * 10 + (y[i] - '0' )) % MOD; } // Compute the product of newX // and newY modulo MOD int ans = newX * newY % MOD; // Return the product return ans; } // Driver Code public static void Main() { int N = 2, X = 13, Y = 22; // Function call int answer = MinProduct(N, X, Y); Console.WriteLine(answer); } } |
Javascript
const MOD = 998244353; // Function to Minimize product of two // integers by swapping any number // of their digits function minProduct(N, X, Y) { // Storing both integers in strings let x = X.toString(); let y = Y.toString(); // Initializing two variables to store // the updated values of X and Y such // that the product is minimized let newX = 0; let newY = 0; // Iterating through all the digits of x and y for (let i = 0; i < N; i++) { // If current digit of x is greater // than that of y, we apply // the operation if (x[i] > y[i]) { [x, y] = [y, x]; } // Update the values of newX and newY newX = (newX * 10 + parseInt(x[i])) % MOD; newY = (newY * 10 + parseInt(y[i])) % MOD; } // Compute the product of newX // and newY modulo MOD const ans = (newX * newY) % MOD; // Return the product return ans; } // Driver code const N = 2; const X = 13; const Y = 22; // Function call const answer = minProduct(N, X, Y); console.log(answer); |
276
Time Complexity: O(N)
Auxiliary Space: O(1)