Dados dos enteros positivos de N dígitos X e Y , la tarea es encontrar la mínima diferencia absoluta posible entre ambos enteros reorganizando los dígitos de ambos enteros en el mismo orden.
Ejemplos:
Entrada: X = 5181 , Y = 3663
Salida: 1482
Explicación:
Reorganizar los dígitos de ambos enteros dados en el orden de (3, 2, 4, 1) modifica el valor de X e Y como 8115 y 6633 respectivamente.
Por tanto, la diferencia absoluta entre ambos es (8115 – 6633) = 1482, que es la mínima diferencia posible.Entrada: X = 37198 , Y = 44911
Salida: 1278
Enfoque: el problema dado se puede resolver encontrando la diferencia absoluta entre cada permutación de X e Y que tienen el mismo orden de reordenamientos de dígitos. Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2D arr[2][N] , que almacena los dígitos de los números X e Y respectivamente.
- Inicialice una array, digamos P[] , que almacene la permutación de los números [0, N – 1] .
- Inicialice una variable, digamos minDIff que almacene la diferencia minimizada entre X e Y.
- Recorra todas las permutaciones posibles de P[] y realice los siguientes pasos:
- Reorganice los dígitos de X e Y según la permutación y almacene la diferencia absoluta entre ellos en una variable, digamos diferencia .
- Después de los pasos anteriores, actualice el valor de minDiff como el mínimo de minDiff y difference .
- Después de completar los pasos anteriores, imprima el valor de minDIff como la diferencia mínima.
A continuación se muestra la implementación del enfoque anterior:
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 order
int 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 Code
int main()
{
int X = 37198, Y = 44911;
cout << minDifference(X, Y);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
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 = 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 Code
public 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 approach
import itertools
# Function to find minimum difference
# between X and Y after rearranging
# their digits in the same order
def 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 code
if __name__ == '__main__':
X = 37198
Y = 44911
print(minDifference(X, Y))
# This code is contributed by MuskanKalra1
C#
// C# program for the above approach
using 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>
Producción
1278
Complejidad temporal: O(N!)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA