Dado un número N en forma de string. La tarea es encontrar el número más grande que tenga el mismo conjunto de dígitos que N y sea más pequeño que N. Si no es posible encontrar ese número, imprima «no es posible».
Ejemplos :
Input: N = "218765" Output: 218756 Input: N = "1234" Output: Not Possible Input: N = "262345" Output: 256432
Las siguientes son algunas observaciones sobre el mayor número menor que N:
- Si todos los dígitos están ordenados en orden ascendente, la salida siempre es «No posible». Por ejemplo, 1234.
- Si todos los dígitos están ordenados en orden descendente, entonces necesitamos intercambiar los dos últimos dígitos. Por ejemplo, 4321.
- Para otros casos, necesitamos procesar el número del lado derecho (¿por qué? Porque necesitamos encontrar el mayor de todos los números más pequeños).
Algoritmo :
- Recorra el número dado desde el dígito más a la derecha, siga recorriendo hasta que encuentre un dígito que sea mayor que el dígito recorrido anteriormente. Por ejemplo, si el número de entrada es «262345», nos detenemos en 6 porque 6 es mayor que el dígito anterior 5. Si no encontramos ese dígito, la salida es «No posible».
- Ahora busque en el lado derecho del dígito anterior ‘d’ el dígito más grande menor que ‘d’. Para “262345?, el lado derecho de 6 contiene “2345”. El mayor dígito menor que 6 es 5.
- Intercambie los dos dígitos encontrados arriba, obtenemos «252346» en el ejemplo anterior.
- Ahora ordene todos los dígitos desde la posición junto a ‘d’ hasta el final del número en orden descendente. El número que obtenemos después de ordenar es la salida. Para el ejemplo anterior, ordenamos los dígitos en negrita 25 2346 . Obtenemos 256432 , que es el número más pequeño anterior para la entrada 262345 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find previous number
void findPrevious(string number, int n)
{
int i, j;
// I) Start from the right most digit
// and find the first digit that is
// smaller than the digit next to it.
for (i = n - 1; i > 0; i--)
if (number[i] < number[i - 1])
break;
// If no such digit is found
// then all digits are in ascending order
// means there cannot be a smallest number
// with same set of digits
if (i == 0) {
cout << "Previous number is not possible";
return;
}
// II) Find the greatest digit on
// right side of (i-1)'th digit that is
// smaller than number[i-1]
int x = number[i - 1], greatest = i;
for (j = i; j < n; j++)
if (number[j] < x && number[j] > number[greatest])
greatest = j;
// III) Swap the above found smallest digit with number[i-1]
swap(number[greatest], number[i - 1]);
// IV) Sort the digits after (i-1) in descending order
sort(number.begin() + i, number.begin() + n, greater<char>());
cout << "Greatest smaller number with same set of digits is " << number;
return;
}
// Driver code
int main()
{
string digits = "262345";
int n = digits.length();
findPrevious(digits, n);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
// Function to find previous number
static void findPrevious(char[] number, int n)
{
int i, j;
// I) Start from the right most digit
// and find the first digit that is
// smaller than the digit next to it.
for (i = n - 1; i > 0; i--)
{
if (number[i] < number[i - 1])
{
break;
}
}
// If no such digit is found
// then all digits are in ascending order
// means there cannot be a smallest number
// with same set of digits
if (i == 0)
{
System.out.print("Previous number is not possible");
return;
}
// II) Find the greatest digit on
// right side of (i-1)'th digit that is
// smaller than number[i-1]
int x = number[i - 1], greatest = i;
for (j = i; j < n; j++)
{
if (number[j] < x && number[j] > number[greatest])
{
greatest = j;
}
}
// III) Swap the above found smallest digit with number[i-1]
swap(number, greatest, i - 1);
// IV) Sort the digits after (i-1) in descending order
Arrays.sort(number, i, n);
reverse(number, i, n - 1);
System.out.print("Greatest smaller number with" +
"same set of digits is " + String.valueOf(number));
return;
}
static String swap(char[] ch, int i, int j)
{
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return String.valueOf(ch);
}
static void reverse(char str[], int start, int end)
{
// Temporary variable to store character
char temp;
while (start <= end)
{
// Swapping the first and last character
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
// Driver code
public static void main(String[] args)
{
String digits = "262345";
int n = digits.length();
findPrevious(digits.toCharArray(), n);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 implementation of the above approach
# Function to find previous number
def findPrevious(number, n):
# This is necessary as strings
# do not support item assignment
number = list(number)
i, j = -1, -1
# I) Start from the right most digit
# and find the first digit that is
# smaller than the digit next to it.
for i in range(n - 1, 0, -1):
if number[i] < number[i - 1]:
break
# If no such digit is found
# then all digits are in ascending order
# means there cannot be a smallest number
# with same set of digits
if i == 0:
print("Previous number is not possible")
return
x, greatest = number[i - 1], i
# II) Find the greatest digit on
# right side of(i-1)'th digit that is
# smaller than number[i-1]
for j in range(i, n):
if (number[j] < x and
number[j] > number[greatest]):
greatest = j
# III) Swap the above found smallest digit
# with number[i-1]
(number[greatest],
number[i - 1]) = (number[i - 1],
number[greatest])
l = number[i:]
del number[i:]
# IV) Sort the digits after(i-1)
# in descending order
l.sort(reverse = True)
number += l
# Again join the list to make it string
number = '' . join(number)
print("Greatest smaller number with",
"same set of digits is", number)
return
# Driver Code
if __name__ == "__main__":
digits = "262345"
n = len(digits)
findPrevious(digits, n)
# This code is contributed by sanjeev2552
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find previous number
static void findPrevious(char[] number, int n)
{
int i, j;
// I) Start from the right most digit
// and find the first digit that is
// smaller than the digit next to it.
for (i = n - 1; i > 0; i--)
{
if (number[i] < number[i - 1])
{
break;
}
}
// If no such digit is found
// then all digits are in ascending order
// means there cannot be a smallest number
// with same set of digits
if (i == 0)
{
Console.Write("Previous number is not possible");
return;
}
// II) Find the greatest digit on
// right side of (i-1)'th digit that is
// smaller than number[i-1]
int x = number[i - 1], greatest = i;
for (j = i; j < n; j++)
{
if (number[j] < x && number[j] > number[greatest])
{
greatest = j;
}
}
// III) Swap the above found
// smallest digit with number[i-1]
swap(number, greatest, i - 1);
// IV) Sort the digits after (i-1) in descending order
Array.Sort(number, i, n-i);
reverse(number, i, n - 1);
Console.Write("Greatest smaller number with" +
"same set of digits is " + String.Join("",number));
return;
}
static String swap(char[] ch, int i, int j)
{
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return String.Join("",ch);
}
static void reverse(char []str, int start, int end)
{
// Temporary variable to store character
char temp;
while (start <= end)
{
// Swapping the first and last character
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
// Driver code
public static void Main(String[] args)
{
String digits = "262345";
int n = digits.Length;
findPrevious(digits.ToCharArray(), n);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript implementation of the above approach
// Function to find previous number
function findPrevious(number, n)
{
let i, j;
// I) Start from the right most digit
// and find the first digit that is
// smaller than the digit next to it.
for(i = n - 1; i > 0; i--)
{
if (number[i] < number[i - 1])
{
break;
}
}
// If no such digit is found then all
// digits are in ascending order means
// there cannot be a smallest number
// with same set of digits
if (i == 0)
{
document.write("Previous number " +
"is not possible");
return;
}
// II) Find the greatest digit on right
// side of (i-1)'th digit that is smaller
// than number[i-1]
let x = number[i - 1], greatest = i;
for(j = i; j < n; j++)
{
if (number[j] < x && number[j] >
number[greatest])
{
greatest = j;
}
}
// III) Swap the above found smallest
// digit with number[i-1]
swap(number, greatest, i - 1);
// IV) Sort the digits after (i-1)
// in descending order
number = number.slice(0, i).concat(
number.slice(i, n).sort(
function(a, b){return b - a;}));
document.write("Greatest smaller number with " +
"same set of digits is " +
(number).join(""));
return;
}
function swap(ch, i, j)
{
let temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return String.valueOf(ch);
}
function reverse(str, start, end)
{
// Temporary variable to store character
let temp;
while (start <= end)
{
// Swapping the first and last character
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
// Driver code
let digits = "262345";
let n = digits.length;
findPrevious(digits.split(""), n);
// This code is contributed by rag2127
</script>
Producción:
Greatest smaller number with same set of digits is 256432
Complejidad de tiempo: O (nlogn), donde n representa la longitud de la string dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA