Encuentre el número más pequeño (sin ceros a la izquierda) que se puede obtener reorganizando los dígitos de un número dado.
Ejemplos:
Input: n = 846903 Output: 304689 Input: n = 55010 Output: 10055 Input: n = -40505 Output: -55400
Pasos para encontrar el número más pequeño.
- Cuente la frecuencia de cada dígito en el número.
- Si es un número no negativo entonces
- Coloque el dígito más pequeño (excepto 0) en la parte más a la izquierda del número requerido.
y disminuya la frecuencia de ese dígito en 1. - Coloque todos los dígitos restantes en orden ascendente de izquierda a derecha.
- Coloque el dígito más pequeño (excepto 0) en la parte más a la izquierda del número requerido.
- De lo contrario, si es un número negativo, entonces
- Coloque el dígito más grande a la izquierda del número requerido. y disminuya la frecuencia de ese dígito en 1.
- Coloque todos los dígitos restantes en orden descendente de derecha a izquierda.
Esta solución se basa en la ordenación por conteo .
C++
// C++ program for finding smallest number
// from digits of given number
#include<iostream>
using namespace std;
// function to find the smallest number
int smallest(int num)
{
// initialize frequency of each digit to Zero
int freq[10] = {0};
// Checking Number is positive or Negative
bool is_pos = (num>0);
// Getting the absolute value of num
num = abs(num);
// count frequency of each digit in the number
while (num)
{
int d = num % 10; // extract last digit
freq[d]++; // increment counting
num = num / 10; //remove last digit
}
int result = 0;
// If it is positive Number then it should be smallest
if(is_pos)
{
// Set the Leftmost digit to minimum except 0
for (int i = 1 ; i <= 9 ; i++)
{
if (freq[i])
{
result = i;
freq[i]--;
break;
}
}
// arrange all remaining digits
// in ascending order
for (int i = 0 ; i <= 9 ; i++)
while (freq[i]--)
result = result * 10 + i;
}
else // If negative then number should be Largest
{
// Set the Leftmost digit to maximum
for (int i = 9 ; i >= 1 ; i--)
{
if (freq[i])
{
result = i;
freq[i]--;
break;
}
}
// arrange all remaining digits
// in descending order
for (int i = 9 ; i >=0 ; i--)
while (freq[i]--)
result = result * 10 + i;
// Negative number should be returned here
result = -result;
}
return result;
}
// Driver Program
int main()
{
int num = 570107;
cout << smallest(num) << endl;
int num2 = -691005;
cout << smallest(num2);
return 0;
}
Java
import java.lang.Math;
// Java program for finding smallest number
// from digits of given number
public class GFG {
// function to find the smallest number
static int smallest(int num)
{
// initialize frequency of each digit to Zero
int[] freq = new int[10];
// Checking Number is positive or Negative
boolean is_pos = (num>0);
// Getting the absolute value of num
num = Math.abs(num);
// count frequency of each digit in the number
while (num > 0)
{
int d = num % 10; // extract last digit
freq[d]++; // increment counting
num = num / 10; //remove last digit
}
int result = 0;
// If it is positive Number then it should be smallest
if(is_pos)
{
// Set the LEFTMOST digit to minimum expect 0
for (int i = 1 ; i <= 9 ; i++)
{
if (freq[i] != 0)
{
result = i;
freq[i]--;
break;
}
}
// arrange all remaining digits
// in ascending order
for (int i = 0 ; i <= 9 ; i++)
while (freq[i]-- != 0)
result = result * 10 + i;
}
else // If negative then number should be Largest
{
// Set the Rightmost digit to maximum
for (int i = 9 ; i >= 1 ; i--)
{
if (freq[i] !=0)
{
result = i;
freq[i]--;
break;
}
}
// arrange all remaining digits
// in descending order
for (int i = 9 ; i >=0 ; i--)
while (freq[i]-- != 0)
result = result * 10 + i;
// Negative number should be returned here
result = -result;
}
return result;
}
// Driver Program
public static void main(String args[])
{
int num = 570107;
System.out.println(smallest(num));
int num2 = -691005;
System.out.println(smallest(num2));
}
}
// This code is contributed by Sumit Ghosh
Python3
# Function to find the smallest number def smallest(lst): # Here i is index and n is the number of the list for i,n in enumerate(lst): # Checking for the first non-zero digit in the sorted list if n != '0': # Remove and store the digit from the lst tmp = lst.pop(i) break # Place the first non-zero digit at the starting # and return the final number return str(tmp) + ''.join(lst) # Driver program if __name__ == '__main__': # Converting the given numbers into string to form a list lst = list(str(570107)) lst.sort() # Calling the function using the above list print (smallest(lst)) # This code is contributed by Mahendra Yadav
C#
// C# program for finding smallest
// number from digits of given
// number
using System;
public class GFG {
// function to find the smallest
// number
static int smallest(int num)
{
// initialize frequency of
// each digit to Zero
int[] freq = new int[10];
// count frequency of each
// digit in the number
while (num > 0)
{
// extract last digit
int d = num % 10;
// increment counting
freq[d]++;
//remove last digit
num = num / 10;
}
// Set the LEFTMOST digit to
// minimum expect 0
int result = 0;
for (int i = 1 ; i <= 9 ; i++)
{
if (freq[i] != 0)
{
result = i;
freq[i]--;
break;
}
}
// arrange all remaining digits
// in ascending order
for (int i = 0 ; i <= 9 ; i++)
while (freq[i]-- != 0)
result = result * 10 + i;
return result;
}
// Driver Program
public static void Main()
{
int num = 570107;
Console.WriteLine(smallest(num));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program for finding smallest
// number from digits of given number
// function to find the smallest number
function smallest($num)
{
// initialize frequency of
// each digit to Zero
$freq = array_fill(0, 10, 0);
// count frequency of each
// digit in the number
while ($num)
{
$d = $num % 10; // extract last digit
$freq[$d]++; // increment counting
$num = (int)($num / 10); // remove last digit
}
// Set the LEFTMOST digit
// to minimum expect 0
$result = 0;
for ($i = 1 ; $i <= 9 ; $i++)
{
if ($freq[$i])
{
$result = $i;
$freq[$i]--;
break;
}
}
// arrange all remaining digits
// in ascending order
for ($i = 0 ; $i <= 9 ; $i++)
while ($freq[$i] > 0)
{
$result = $result * 10 + $i;
$freq[$i] -= 1;
}
return $result;
}
// Driver Code
$num = 570107;
echo smallest($num);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program for finding smallest number
// from digits of given number
// function to find the smallest number
function smallest(num)
{
// initialize frequency of each digit to Zero
var freq = Array(10).fill(0);
// count frequency of each digit in the number
while (num)
{
var d = num % 10; // extract last digit
freq[d]++; // increment counting
num = parseInt(num / 10); //remove last digit
}
// Set the LEFTMOST digit to minimum expect 0
var result = 0;
for (var i = 1 ; i <= 9 ; i++)
{
if (freq[i])
{
result = i;
freq[i]--;
break;
}
}
// arrange all remaining digits
// in ascending order
for (var i = 0 ; i <= 9 ; i++)
while (freq[i]--)
result = result * 10 + i;
return result;
}
// Driver Program
var num = 570107;
document.write(smallest(num));
// This code is contributed by rutvik_56.
</script>
Producción
100577 -965100
Otro enfoque: encuentre la permutación más pequeña de un número dado
Este artículo es una contribución de Ajay Kumar Agrahari (aJy aGr) . 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