Dado un entero positivo, encuentre el entero máximo posible haciendo como máximo K operaciones de intercambio en sus dígitos.
Ejemplos:
Input: M = 254, K = 1 Output: 524 Swap 5 with 2 so number becomes 524 Input: M = 254, K = 2 Output: 542 Swap 5 with 2 so number becomes 524 Swap 4 with 2 so number becomes 542 Input: M = 68543, K = 1 Output: 86543 Swap 8 with 6 so number becomes 86543 Input: M = 7599, K = 2 Output: 9975 Swap 9 with 5 so number becomes 7995 Swap 9 with 7 so number becomes 9975 Input: M = 76543, K = 1 Output: 76543 Explanation: No swap is required. Input: M = 129814999, K = 4 Output: 999984211 Swap 9 with 1 so number becomes 929814991 Swap 9 with 2 so number becomes 999814291 Swap 9 with 8 so number becomes 999914281 Swap 1 with 8 so number becomes 999984211
Solución ingenua:
Enfoque: la idea es considerar cada dígito e intercambiarlo con dígitos que lo siguen uno a la vez y ver si conduce al número máximo. El proceso se repite K veces. El código se puede optimizar aún más, si el dígito actual se intercambia con un dígito menor que el dígito siguiente.
Algoritmo:
- Cree una variable global que almacenará la string o el número máximo.
- Defina una función recursiva que tome la string como número y valor de k
- Ejecute un ciclo anidado, el ciclo externo desde 0 hasta la longitud de la string -1 y el ciclo interno desde i+1 hasta el final de la string.
- Intercambie el carácter i-ésimo y j-ésimo y verifique si la string ahora es máxima y actualice la string máxima.
- Llame a la función recursivamente con los parámetros: string y k-1.
- Ahora vuelva a intercambiar el carácter i-ésimo y j-ésimo.
C++
// C++ program to find maximum
// integer possible by doing
// at-most K swap operations
// on its digits.
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum
// integer possible by
// doing at-most K swap
// operations on its digits
void findMaximumNum(
string str, int k, string& max)
{
// Return if no swaps left
if (k == 0)
return;
int n = str.length();
// Consider every digit
for (int i = 0; i < n - 1; i++) {
// Compare it with all digits after it
for (int j = i + 1; j < n; j++) {
// if digit at position i
// is less than digit
// at position j, swap it
// and check for maximum
// number so far and recurse
// for remaining swaps
if (str[i] < str[j]) {
// swap str[i] with str[j]
swap(str[i], str[j]);
// If current num is more
// than maximum so far
if (str.compare(max) > 0)
max = str;
// recurse of the other k - 1 swaps
findMaximumNum(str, k - 1, max);
// Backtrack
swap(str[i], str[j]);
}
}
}
}
// Driver code
int main()
{
string str = "129814999";
int k = 4;
string max = str;
findMaximumNum(str, k, max);
cout << max << endl;
return 0;
}
Java
// Java program to find maximum
// integer possible by doing
// at-most K swap operations
// on its digits.
import java.util.*;
class GFG{
static String max;
// Function to find maximum
// integer possible by
// doing at-most K swap
// operations on its digits
static void findMaximumNum(char[] str,
int k)
{
// Return if no swaps left
if (k == 0)
return;
int n = str.length;
// Consider every digit
for (int i = 0; i < n - 1; i++)
{
// Compare it with all digits
// after it
for (int j = i + 1; j < n; j++)
{
// if digit at position i
// is less than digit
// at position j, swap it
// and check for maximum
// number so far and recurse
// for remaining swaps
if (str[i] < str[j])
{
// swap str[i] with
// str[j]
char t = str[i];
str[i] = str[j];
str[j] = t;
// If current num is more
// than maximum so far
if (String.valueOf(str).compareTo(max) > 0)
max = String.valueOf(str);
// recurse of the other
// k - 1 swaps
findMaximumNum(str, k - 1);
// Backtrack
char c = str[i];
str[i] = str[j];
str[j] = c;
}
}
}
}
// Driver code
public static void main(String[] args)
{
String str = "129814999";
int k = 4;
max = str;
findMaximumNum(str.toCharArray(), k);
System.out.print(max + "\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find maximum # integer possible by doing at-most # K swap operations on its digits. # utility function to swap two # characters of a string def swap(string, i, j): return (string[:i] + string[j] + string[i + 1:j] + string[i] + string[j + 1:]) # function to find maximum integer # possible by doing at-most K swap # operations on its digits def findMaximumNum(string, k, maxm): # return if no swaps left if k == 0: return n = len(string) # consider every digit for i in range(n - 1): # and compare it with all digits after it for j in range(i + 1, n): # if digit at position i is less than # digit at position j, swap it and # check for maximum number so far and # recurse for remaining swaps if string[i] < string[j]: # swap string[i] with string[j] string = swap(string, i, j) # If current num is more than # maximum so far if string > maxm[0]: maxm[0] = string # recurse of the other k - 1 swaps findMaximumNum(string, k - 1, maxm) # backtrack string = swap(string, i, j) # Driver Code if __name__ == "__main__": string = "129814999" k = 4 maxm = [string] findMaximumNum(string, k, maxm) print(maxm[0]) # This code is contributed # by vibhu4agarwal
C#
// C# program to find maximum
// integer possible by doing
// at-most K swap operations
// on its digits.
using System;
class GFG{
static String max;
// Function to find maximum
// integer possible by
// doing at-most K swap
// operations on its digits
static void findMaximumNum(char[] str,
int k)
{
// Return if no swaps left
if (k == 0)
return;
int n = str.Length;
// Consider every digit
for (int i = 0; i < n - 1; i++)
{
// Compare it with all digits
// after it
for (int j = i + 1; j < n; j++)
{
// if digit at position i
// is less than digit
// at position j, swap it
// and check for maximum
// number so far and recurse
// for remaining swaps
if (str[i] < str[j])
{
// swap str[i] with
// str[j]
char t = str[i];
str[i] = str[j];
str[j] = t;
// If current num is more
// than maximum so far
if (String.Join("", str).CompareTo(max) > 0)
max = String.Join("", str);
// recurse of the other
// k - 1 swaps
findMaximumNum(str, k - 1);
// Backtrack
char c = str[i];
str[i] = str[j];
str[j] = c;
}
}
}
}
// Driver code
public static void Main(String[] args)
{
String str = "129814999";
int k = 4;
max = str;
findMaximumNum(str.ToCharArray(), k);
Console.Write(max + "\n");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to find maximum
// integer possible by doing
// at-most K swap operations
// on its digits.
let max;
// Function to find maximum
// integer possible by
// doing at-most K swap
// operations on its digits
function findMaximumNum(str,k)
{
// Return if no swaps left
if (k == 0)
return;
let n = str.length;
// Consider every digit
for (let i = 0; i < n - 1; i++)
{
// Compare it with all digits
// after it
for (let j = i + 1; j < n; j++)
{
// if digit at position i
// is less than digit
// at position j, swap it
// and check for maximum
// number so far and recurse
// for remaining swaps
if (str[i] < str[j])
{
// swap str[i] with
// str[j]
let t = str[i];
str[i] = str[j];
str[j] = t;
// If current num is more
// than maximum so far
if ((str).join("")>(max) )
max = (str).join("");
// recurse of the other
// k - 1 swaps
findMaximumNum(str, k - 1);
// Backtrack
let c = str[i];
str[i] = str[j];
str[j] = c;
}
}
}
}
// Driver code
let str = "129814999";
let k = 4;
max = str;
findMaximumNum(str.split(""), k);
document.write(max + "<br>");
// This code is contributed by unknown2108
</script>
Producción:
999984211
Análisis de Complejidad:
- Complejidad de tiempo: O((n^2)^k).
Por cada llamada recursiva, se generan n^2 llamadas recursivas hasta que el valor de k es 0. Por lo tanto, el total de llamadas recursivas es O((n^2)^k). - Complejidad espacial: O(n).
Este es el espacio necesario para almacenar la string de salida.
Solución eficiente :
enfoque: el enfoque anterior atraviesa toda la string en cada llamada recursiva, lo que es altamente ineficiente e innecesario. Además, calcular previamente el dígito máximo después del actual en una llamada recursiva evita intercambios innecesarios con cada dígito. Se puede observar que para hacer la string máxima, el dígito máximo se desplaza al frente. Entonces, en lugar de probar todos los pares, pruebe solo aquellos pares en los que uno de los elementos es el dígito máximo que aún no se ha intercambiado al frente.
Hay una mejora de 27580 microsegundos para cada caso de prueba .
Algoritmo:
- Cree una variable global que almacenará la string o el número máximo.
- Defina una función recursiva que tome la string como un número, el valor de k y el índice actual.
- Encuentre el índice del elemento máximo en el índice actual del rango hasta el final.
- si el índice del elemento máximo no es igual al índice actual, disminuya el valor de k.
- Ejecute un ciclo desde el índice actual hasta el final de la array
- Si el dígito i es igual al elemento máximo
- Intercambie el i-ésimo y el elemento en el índice actual y verifique si la string ahora es máxima y actualice la string máxima.
- Llame a la función recursivamente con los parámetros: string y k.
- Ahora vuelva a intercambiar el i-ésimo y el elemento en el índice actual.
C++
// C++ program to find maximum
// integer possible by doing
// at-most K swap operations on
// its digits.
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum
// integer possible by
// doing at-most K swap operations
// on its digits
void findMaximumNum(
string str, int k,
string& max, int ctr)
{
// return if no swaps left
if (k == 0)
return;
int n = str.length();
// Consider every digit after
// the cur position
char maxm = str[ctr];
for (int j = ctr + 1; j < n; j++) {
// Find maximum digit greater
// than at ctr among rest
if (maxm < str[j])
maxm = str[j];
}
// If maxm is not equal to str[ctr],
// decrement k
if (maxm != str[ctr])
--k;
// search this maximum among the rest from behind
//first swap the last maximum digit if it occurs more than 1 time
//example str= 1293498 and k=1 then max string is 9293418 instead of 9213498
for (int j = n-1; j >=ctr; j--) {
// If digit equals maxm swap
// the digit with current
// digit and recurse for the rest
if (str[j] == maxm) {
// swap str[ctr] with str[j]
swap(str[ctr], str[j]);
// If current num is more than
// maximum so far
if (str.compare(max) > 0)
max = str;
// recurse other swaps after cur
findMaximumNum(str, k, max, ctr + 1);
// Backtrack
swap(str[ctr], str[j]);
}
}
}
// Driver code
int main()
{
string str = "129814999";
int k = 4;
string max = str;
findMaximumNum(str, k, max, 0);
cout << max << endl;
return 0;
}
Java
// Java program to find maximum
// integer possible by doing
// at-most K swap operations on
// its digits.
import java.io.*;
class Res {
static String max = "";
}
class Solution {
// Function to set highest possible digits at given
// index.
public static void findMaximumNum(char ar[], int k,
Res r)
{
if (k == 0)
return;
int n = ar.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// if digit at position i is less than digit
// at position j, we swap them and check for
// maximum number so far.
if (ar[j] > ar[i]) {
char temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
String st = new String(ar);
// if current number is more than
// maximum so far
if (r.max.compareTo(st) < 0) {
r.max = st;
}
// calling recursive function to set the
// next digit.
findMaximumNum(ar, k - 1, r);
// backtracking
temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
}
}
}
}
// Function to find the largest number after k swaps.
public static void main(String[] args)
{
String str = "129814999";
int k = 4;
Res r = new Res();
r.max = str;
findMaximumNum(str.toCharArray(), k, r);
//Print the answer stored in res class
System.out.println(r.max);
}
}
Python3
# Python3 program to find maximum # integer possible by doing at-most # K swap operations on its digits. # function to find maximum integer # possible by doing at-most K swap # operations on its digits def findMaximumNum(string, k, maxm, ctr): # return if no swaps left if k == 0: return n = len(string) # Consider every digit after # the cur position mx = string[ctr] for i in range(ctr+1,n): # Find maximum digit greater # than at ctr among rest if int(string[i]) > int(mx): mx=string[i] # If maxm is not equal to str[ctr], # decrement k if(mx!=string[ctr]): k=k-1 # search this maximum among the rest from behind # first swap the last maximum digit if it occurs more than 1 time # example str= 1293498 and k=1 then max string is 9293418 instead of 9213498 for i in range(ctr,n): # If digit equals maxm swap # the digit with current # digit and recurse for the rest if(string[i]==mx): # swap str[ctr] with str[j] string[ctr], string[i] = string[i], string[ctr] new_str = "".join(string) # If current num is more than # maximum so far if int(new_str) > int(maxm[0]): maxm[0] = new_str # recurse of the other k - 1 swaps findMaximumNum(string, k , maxm, ctr+1) # backtrack string[ctr], string[i] = string[i], string[ctr] # Driver Code if __name__ == "__main__": string = "129814999" k = 4 maxm = [string] string = [char for char in string] findMaximumNum(string, k, maxm, 0) print(maxm[0]) # This code is contributed Aarti_Rathi
C#
// C# program to find maximum
// integer possible by doing
// at-most K swap operations on
// its digits.
using System;
class Res {
public String max = "";
}
public class Solution {
// Function to set highest possible digits at given
// index.
static void findMaximumNum(char []ar, int k,
Res r)
{
if (k == 0)
return;
int n = ar.Length;
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
// if digit at position i is less than digit
// at position j, we swap them and check for
// maximum number so far.
if (ar[j] > ar[i]) {
char temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
String st = new String(ar);
// if current number is more than
// maximum so far
if (r.max.CompareTo(st) < 0) {
r.max = st;
}
// calling recursive function to set the
// next digit.
findMaximumNum(ar, k - 1, r);
// backtracking
temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
}
}
}
}
// Function to find the largest number after k swaps.
public static void Main(String[] args)
{
String str = "129814999";
int k = 4;
Res r = new Res();
r.max = str;
findMaximumNum(str.ToCharArray(), k, r);
// Print the answer stored in res class
Console.WriteLine(r.max);
}
}
// This code is contributed by shikhasingrajput
Producción:
999984211
Análisis de Complejidad:
- Complejidad temporal: O(n^k).
Para cada llamada recursiva, se generan n llamadas recursivas hasta que el valor de k es 0. Por lo tanto, el total de llamadas recursivas es O((n)^k). - Complejidad espacial: O(n).
El espacio necesario para almacenar la string de salida.
Ejercicio:
- Encuentre el número entero mínimo posible haciendo al menos K operaciones de intercambio en sus dígitos.
- Encuentre el número entero máximo/mínimo posible haciendo exactamente K operaciones de intercambio en sus dígitos.
Este artículo es una contribución de Aarti Rathi y Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA