Dados dos números N y M. Construya el número máximo permutando (cambiando de orden) los dígitos de N, sin exceder M.
Nota: Se permite dejar N como está.
Ejemplos:
Entrada: N = 123, M = 222
Salida: 213
¡Hay un total de 3! permutaciones posibles para N = 123, pero la única permutación que satisface la condición dada es 213. De manera similar, en el ejemplo 2, ¡hay un total de 4! permutaciones posibles para N = 3921, pero la única permutación que satisface la condición dada es 9321.
Entrada: N = 3921, M = 10000
Salida: 9321
Enfoque: Construyamos la respuesta dígito por dígito comenzando desde el extremo izquierdo. Se nos pide que construyamos una respuesta lexicográficamente máxima. Entonces, en este orden, debemos elegir el dígito más grande en cada paso. El enfoque es iterar sobre todos los dígitos posibles a partir del mayor. Para cada dígito, verifique si es posible colocarlo en esta posición y compare el número resultante con el número M. Si es menor o igual que el valor de M, continúe con el siguiente dígito.
A continuación se muestra la implementación de CPP del enfoque anterior:
CPP
// CPP program to Maximize the given number.
#include <bits/stdc++.h>
using namespace std;
// Function to maximize the number N with
// limit as M.
string maximizeNumber(string N, int M)
{
// Sorting the digits of the
// number in increasing order.
sort(N.begin(), N.end());
for (int i = 0; i < N.size(); i++) {
for (int j = i + 1; j < N.size(); j++) {
// Copying the string into another
// temp string.
string t = N;
// Swapping the j-th char(digit)
// with i-th char(digit)
swap(t[j], t[i]);
// Sorting the temp string
// from i-th pos to end.
sort(t.begin() + i + 1, t.end());
// Checking if the string t is
// greater than string N and less
// than or equal to the number M.
if (stoll(t) > stoll(N) && stoll(t) <= M)
// If yes then, we will permanently
// swap the i-th char(or digit)
// with j-th char(digit).
swap(N[i], N[j]);
}
}
// Returns the maximized number.
return N;
}
// Driver function
int main()
{
string N = "123";
int M = 222;
cout << maximizeNumber(N, M);
return 0;
}
// This code is contributed by KaaL-EL.
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.Arrays;
class GFG {
// Java has no built-in swap function.
public static String swap(String str, int i, int j)
{
char ch[] = str.toCharArray();
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return new String(ch);
}
// Since STRINGS are immutable in Java, first we have to
// convert it to a character array in order to sort.
public static String
sortString(String string, int s_index, int e_index)
{
char tempArray[] = string.toCharArray();
// Sorting temp array using
Arrays.sort(tempArray, s_index, e_index);
// returning the new sorted string
return new String(tempArray);
}
public static String maximizeNumber(String N, int M)
{
// Sorting the digits of the
// number in increasing order.
N = sortString(N, 0, N.length());
for (int i = 0; i < N.length(); i++) {
for (int j = i + 1; j < N.length(); j++) {
// Copying the string into another
// temp string.
String t = N;
// Swapping the j-th char(digit)
// with i-th char(digit)
t = swap(t, j, i);
// Sorting the temp string
// from i-th pos to end.
t = sortString(t, i + 1, t.length());
// Checking if the string t is
// greater than string N and less
// than or equal to the number M.
if (Long.parseLong(t) > Long.parseLong(N)
&& Long.parseLong(t) <= M)
// If yes then, we will permanently
// swap the i-th char(or digit)
// with j-th char(digit).
N = swap(N, i, j);
}
}
// Returns the maximized number.
return N;
}
// Driver Code
public static void main(String[] args)
{
String N = "123";
int M = 222;
System.out.println(maximizeNumber(N, M));
}
}
//This code is contributed by KaaL-EL.
C#
// C# program to implement the approach
using System;
using System.Collections.Generic;
class GFG {
// C# has no built-in swap function.
public static string swap(String str, int i, int j)
{
char[] ch = str.ToCharArray();
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return new string(ch);
}
// Since STRINGS are immutable in C#, first we have to
// convert it to a character array in order to sort.
public static string sortString(string str, int s_index,
int e_index)
{
char[] tempArray = str.ToCharArray();
// Sorting temp array using
Array.Sort(tempArray, s_index, e_index - s_index);
// returning the new sorted string
return new string(tempArray);
}
public static string maximizeNumber(string N, int M)
{
// Sorting the digits of the
// number in increasing order.
N = sortString(N, 0, N.Length);
for (int i = 0; i < N.Length; i++) {
for (int j = i + 1; j < N.Length; j++) {
// Copying the string into another
// temp string.
string t = N;
// Swapping the j-th char(digit)
// with i-th char(digit)
t = swap(t, j, i);
// Sorting the temp string
// from i-th pos to end.
t = sortString(t, i + 1, t.Length);
// Checking if the string t is
// greater than string N and less
// than or equal to the number M.
if (Convert.ToInt64(t) > Convert.ToInt64(N)
&& Convert.ToInt64(t) <= M)
// If yes then, we will permanently
// swap the i-th char(or digit)
// with j-th char(digit).
N = swap(N, i, j);
}
}
// Returns the maximized number.
return N;
}
// Driver Code
public static void Main(string[] args)
{
string N = "123";
int M = 222;
Console.WriteLine(maximizeNumber(N, M));
}
}
// This code is contributed by phasing17
Javascript
// JavaScript program to implement the approach
// JavaScript has no built-in swap function.
function swap(str, i, j)
{
let ch = str.split("");
let temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return ch.join("");
}
// Since STRINGS are immutable in JavaScript, first we have
// to convert it to a character array in order to sort.
function sortString(str, s_index, e_index)
{
let tempArray = str.split("");
// Sorting temp array using
tempArray
= tempArray.slice(0, s_index)
.concat(
tempArray.slice(s_index, e_index).sort());
// returning the new sorted string
return tempArray.join("");
}
function maximizeNumber(N, M)
{
// Sorting the digits of the
// number in increasing order.
N = sortString(N, 0, N.length);
for (var i = 0; i < N.length; i++) {
for (var j = i + 1; j < N.length; j++) {
// Copying the string into another
// temp string.
let t = N;
// Swapping the j-th char(digit)
// with i-th char(digit)
t = swap(t, j, i);
// Sorting the temp string
// from i-th pos to end.
t = sortString(t, i + 1, t.length);
// Checking if the string t is
// greater than string N and less
// than or equal to the number M.
if (parseInt(t) > parseInt(N)
&& parseInt(t) <= M)
// If yes then, we will permanently
// swap the i-th char(or digit)
// with j-th char(digit).
N = swap(N, i, j);
}
}
// Returns the maximized number.
return N;
}
// Driver Code
let N = "123";
let M = 222;
console.log(maximizeNumber(N, M));
// This code is contributed by phasing17
Producción:
213
Complejidad del tiempo: O(n 3 log n)
Espacio Auxiliar: O(n), ya que se han tomado n espacios extra.
Este artículo es una contribución de Aarti_Rathi . 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 Sagar Shukla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA