Dados dos números A y B , la tarea es encontrar la disposición de los dígitos de A tal que sea justo mayor que el número dado B , es decir, encontrar la permutación de valor mínimo de A mayor que B . Si no es posible tal permutación, imprima -1
Ejemplos:
Entrada: A = 9236, B = 3125
Salida: 3269
Explicación:
El número mínimo mayor que 3125 formado a partir de los dígitos de A es 3269.
Entrada: A = 1234, B = 9879
Salida: -1
Enfoque: la idea es usar next_permutation() y stol() . Se pueden seguir los siguientes pasos para calcular la respuesta:
- Tome ambos números como entrada de string para hacer uso de next_permutation() .
- Use stol() para encontrar el valor largo de B .
- Luego encuentra la permutación más baja del número A.
- Para cada permutación de A , comprueba si el número es mayor que B.
- Si alguna permutación es mayor que el número B, entonces es una de las posibles respuestas. Seleccione la mínima de todas las respuestas posibles.
- Si tal número no está presente, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to find the greater permutation
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 999999999999999999
// Function to find the greater permutation
ll solve(string a, string b)
{
ll n, val, ans = inf;
// Convert the string B to long
val = stol(b);
n = a.length();
// To find the lowest permutation
// of the number
sort(a.begin(), a.end());
// Find if the lowest permutation of A is
// greater than the given number B
if (stol(a) > val) {
ans = min((ll)stol(a), ans);
}
// Find all the permutations of A
while (next_permutation(a.begin(),
a.end())) {
if (stol(a) > val) {
ans = min((ll)stol(a), ans);
}
}
// If ans is not the initial value
// then return ans
if (ans != inf) {
return ans;
}
// Else return -1
else {
return -1;
}
}
// Driver code
int main()
{
string a, b;
ll ans;
a = "9236";
b = "3145";
ans = solve(a, b);
cout << ans;
}
Producción:
3269
Complejidad de tiempo:O(n * log n)