Given two N-digit positive integers X and Y, the task is to find the minimum absolute difference between both the integers possible by rearranging the digits of both the integers in the same order.
Examples:
Input: X = 5181, Y = 3663
Output: 1482
Explanation:
Rearranging the digits of both the given integers in the order of (3, 2, 4, 1) modifies the value of X and Y as 8115 and 6633 respectively.
Therefore, the absolute difference between the two is (8115 – 6633) = 1482, which is the minimum possible difference.Input: X = 37198, Y = 44911
Output: 1278
Approach: The given problem can be solved by finding the absolute difference between every permutation of X and Y having the same order of rearrangements of digits. Follow the steps below to solve the problem:
- Initialize a 2D array arr[2][N], that stores the digits of numbers X and Y respectively.
- Initialize an array, say P[], that stores the permutation of the numbers [0, N – 1].
- Initialize a variable, say minDIff that stores the minimized difference between X and Y.
- Traverse the all possible permutation of P[] and perform the following steps:
- Rearrange the digits of X and Y according to the permutation and store the absolute difference between them in a variable say difference.
- After the above steps, update the value of minDIff as the minimum of minDiff and difference.
- After completing the above steps, print the value of minDIff as the minimum difference.
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 minimum difference// between X and Y after rearranging// their digits in the same orderint minDifference(int X, int Y){ // Stores the minimum difference int minDiff = INT_MAX; // Stores the number X as string string x = to_string(X); // Stores the number Y as string string y = to_string(Y); // Stores number of digits int n = x.size(); // Store the digits int a[2][n]; // Traverse the range [0, 1] for (int i = 0; i < 2; i++) { // Traverse the range [0, N - 1] for (int j = 0; j < n; j++) { // If the value of i is 0 if (i == 0) a[i][j] = x[j] - '0'; // Otherwise else a[i][j] = y[j] - '0'; } } // Stores the permutation of [1, N] int p[n]; // Initialize the permutation array for (int i = 0; i < n; i++) p[i] = i; // Generate all possible permutation do { // Stores the maximum of X and Y int xx = INT_MIN; // Stores the minimum of X and Y int yy = INT_MAX; // Traverse the range [0, 1] for (int i = 0; i < 2; i++) { // Stores the number // after rearranging int num = 0; // Traverse the range [0, N - 1] for (int j = 0; j < n; j++) // Update the value of num num = num * 10 + a[i][p[j]]; // Update the value of xx xx = max(xx, num); // Update the value of yy yy = min(yy, num); } // Update the value of minDiff minDiff = min(minDiff, xx - yy); } while (next_permutation(p, p + n)); // Return the minimum difference return minDiff;}// Driver Codeint main(){ int X = 37198, Y = 44911; cout << minDifference(X, Y); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find minimum difference// between X and Y after rearranging// their digits in the same orderstatic int minDifference(int X, int Y){ // Stores the minimum difference int minDiff = Integer.MAX_VALUE; // Stores the number X as String String x = String.valueOf(X); // Stores the number Y as String String y = String.valueOf(Y); // Stores number of digits int n = x.length(); // Store the digits int [][]a = new int[2][n]; // Traverse the range [0, 1] for (int i = 0; i < 2; i++) { // Traverse the range [0, N - 1] for (int j = 0; j < n; j++) { // If the value of i is 0 if (i == 0) a[i][j] = x.charAt(j) - '0'; // Otherwise else a[i][j] = y.charAt(j) - '0'; } } // Stores the permutation of [1, N] int []p = new int[n]; // Initialize the permutation array for (int i = 0; i < n; i++) p[i] = i; // Generate all possible permutation do { // Stores the maximum of X and Y int xx = Integer.MIN_VALUE; // Stores the minimum of X and Y int yy = Integer.MAX_VALUE; // Traverse the range [0, 1] for (int i = 0; i < 2; i++) { // Stores the number // after rearranging int num = 0; // Traverse the range [0, N - 1] for (int j = 0; j < n; j++) // Update the value of num num = num * 10 + a[i][p[j]]; // Update the value of xx xx = Math.max(xx, num); // Update the value of yy yy = Math.min(yy, num); } // Update the value of minDiff minDiff = Math.min(minDiff, xx - yy); } while (next_permutation(p)); // Return the minimum difference return minDiff;}static boolean next_permutation(int[] p) { for (int a = p.length - 2; a >= 0; --a) if (p[a] < p[a + 1]) for (int b = p.length - 1;; --b) if (p[b] > p[a]) { int t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } return false; }// Driver Codepublic static void main(String[] args){ int X = 37198, Y = 44911; System.out.print(minDifference(X, Y));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approachimport itertools# Function to find minimum difference# between X and Y after rearranging# their digits in the same orderdef minDifference(X, Y): # Stores the minimum difference minDiff = float("inf") # Stores the number X as string x = str(X) # Stores the number Y as string y = str(Y) # Stores no of digits n = len(x) # store the digits a = [[0 for j in range(n)] for i in range(2)] # Traverse the range [0, 1] for i in range(0, 2): # Traverse the range [0, N - 1] for j in range(n): # If the value of i is 0 if i == 0: a[i][j] = ord(x[j]) - ord('0') elif i == 1: a[i][j] = ord(y[j]) - ord('0') # Stores the permutation of [1, N] p = [0 for i in range(n)] # Initialize the permutation array for i in range(n): p[i] = i # Generating all the permutations # of p using itertools l = itertools.permutations(p, n) # Permutations list below stores # all the permutations genenerated permutations = [] for i in l: permutations.append(list(i)) p = permutations[0] n1 = len(permutations) k = 1 # Generate all possible permutation while True: # Stores the maximum of X and Y xx = float("-inf") # Stores the minimum of X and Y yy = float("inf") # Traverse the range [0, 1] for i in range(0, 2): # Stores the number # after rearranging num = 0 # Traverse the range [0, N - 1] for j in range(0, n): # Update the value of num num = num * 10 + a[i][p[j]] # Update the value of xx xx = max(xx, num) # Update the value of yy yy = min(yy, num) minDiff = min(minDiff, xx - yy) # Break the while loop when we have # iterated over all the permutations if k >= n1: break # Use the next permutation p = permutations[k] k += 1 # Return the minimum difference return minDiff# Driver codeif __name__ == '__main__': X = 37198 Y = 44911 print(minDifference(X, Y))# This code is contributed by MuskanKalra1 |
C#
// C# program for the above approachusing System;class GFG { // Function to find minimum difference // between X and Y after rearranging // their digits in the same order static int minDifference(int X, int Y) { // Stores the minimum difference int minDiff = Int32.MaxValue; // Stores the number X as String string x = X.ToString(); // Stores the number Y as String string y = Y.ToString(); // Stores number of digits int n = x.Length; // Store the digits int[, ] a = new int[2, n]; // Traverse the range [0, 1] for (int i = 0; i < 2; i++) { // Traverse the range [0, N - 1] for (int j = 0; j < n; j++) { // If the value of i is 0 if (i == 0) a[i, j] = x[j] - '0'; // Otherwise else a[i, j] = y[j] - '0'; } } // Stores the permutation of [1, N] int[] p = new int[n]; // Initialize the permutation array for (int i = 0; i < n; i++) p[i] = i; // Generate all possible permutation do { // Stores the maximum of X and Y int xx = Int32.MinValue; // Stores the minimum of X and Y int yy = Int32.MaxValue; // Traverse the range [0, 1] for (int i = 0; i < 2; i++) { // Stores the number // after rearranging int num = 0; // Traverse the range [0, N - 1] for (int j = 0; j < n; j++) // Update the value of num num = num * 10 + a[i, p[j]]; // Update the value of xx xx = Math.Max(xx, num); // Update the value of yy yy = Math.Min(yy, num); } // Update the value of minDiff minDiff = Math.Min(minDiff, xx - yy); } while (next_permutation(p)); // Return the minimum difference return minDiff; } static bool next_permutation(int[] p) { for (int a = p.Length - 2; a >= 0; --a) if (p[a] < p[a + 1]) for (int b = p.Length - 1;; --b) if (p[b] > p[a]) { int t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.Length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } return false; } // Driver Code public static void Main(string[] args) { int X = 37198, Y = 44911; Console.WriteLine(minDifference(X, Y)); }}// This code is contributed by ukasp. |
Javascript
<script> // Javascript program for // the above approach // Function to find minimum difference // between X and Y after rearranging // their digits in the same order function minDifference(X, Y) { // Stores the minimum difference let minDiff = Number.MAX_SAFE_INTEGER; // Stores the number X as String let x = X.toString(); // Stores the number Y as String let y = Y.toString(); // Stores number of digits let n = x.length; // Store the digits let a = []; for (let i = 0; i < 2; i++) { a[i] = new Array(n); } //Traverse the range [0, 1] for (let i = 0; i < 2; i++) { // Traverse the range [0, N - 1] for (let j = 0; j < n; j++) { // If the value of i is 0 if (i == 0) a[i][j] = x.charAt(j) - '0'; // Otherwise else a[i][j] = y.charAt(j) - '0'; } } // Stores the permutation of [1, N] let p = []; // Initialize the permutation array for (let i = 0; i < n; i++) p[i] = i; // Generate all possible permutation do { // Stores the maximum of X and Y let xx = Number.MIN_SAFE_INTEGER; // Stores the minimum of X and Y let yy = Number.MAX_SAFE_INTEGER; // Traverse the range [0, 1] for (let i = 0; i < 2; i++) { // Stores the number // after rearranging let num = 0; // Traverse the range [0, N - 1] for (let j = 0; j < n; j++) // Update the value of num num = num * 10 + a[i][p[j]]; // Update the value of xx xx = Math.max(xx, num); // Update the value of yy yy = Math.min(yy, num); } // Update the value of minDiff minDiff = Math.min(minDiff, xx - yy); } while (next_permutation(p)); // Return the minimum difference return minDiff; } function next_permutation(p) { for (let a = p.length - 2; a >= 0; --a) if (p[a] < p[a + 1]) for (let b = p.length - 1; ; --b) if (p[b] > p[a]) { let t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } return false; } // Driver Code let X = 37198, Y = 44911; document.write(minDifference(X, Y)); // This code is contributed by Hritik </script> |
Output
1278
Time Complexity: O(N!)
Auxiliary Space: O(1)
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!
