Dado un número positivo n, imprima un número menor que n tal que todos sus dígitos sean distintos.
Ejemplos:
Input : 1134 Output : 1098 1098 is the largest number smaller than 1134 such that all digits are distinct. Input : 4559 Output : 4539
El problema se puede resolver fácilmente usando el conteo. En primer lugar, recorra los números menores que n y para cada número cuente la frecuencia de los dígitos usando la array de conteo. Si todos los dígitos ocurren solo una vez, imprimimos ese número. La respuesta siempre existe, por lo que no hay problema de bucle infinito.
C++
// CPP program to find a number less than
// n such that all its digits are distinct
#include <bits/stdc++.h>
using namespace std;
// Function to find a number less than
// n such that all its digits are distinct
int findNumber(int n)
{
// looping through numbers less than n
for (int i = n - 1; >=0 ; i--) {
// initializing a hash array
int count[10] = { 0 };
int x = i; // creating a copy of i
// initializing variables to compare lengths of digits
int count1 = 0, count2 = 0;
// counting frequency of the digits
while (x) {
count[x % 10]++;
x /= 10;
count1++;
}
// checking if each digit is present once
for (int j = 0; j < 10; j++) {
if (count[j] == 1)
count2++;
}
if (count1 == count2)
return i;
}
}
// Driver code
int main()
{
int n = 8490;
cout << findNumber(n);
return 0;
}
Java
// Java program to find a number less than
// n such that all its digits are distinct
class GFG{
// Function to find a number less than
// n such that all its digits are distinct
static int findNumber(int n)
{
// looping through numbers less than n
for (int i = n - 1;i >=0 ; i--) {
// initializing a hash array
int[] count=new int[10];
int x = i; // creating a copy of i
// initializing variables to compare lengths of digits
int count1 = 0, count2 = 0;
// counting frequency of the digits
while (x>0) {
count[x % 10]++;
x /= 10;
count1++;
}
// checking if each digit is present once
for (int j = 0; j < 10; j++) {
if (count[j] == 1)
count2++;
}
if (count1 == count2)
return i;
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int n = 8490;
System.out.println(findNumber(n));
}
}
// This code is contributed by mits
Python3
# python 3 program to find a number less than # n such that all its digits are distinct # Function to find a number less than # n such that all its digits are distinct def findNumber(n): # looping through numbers less than n i = n-1 while(i>=0): # initializing a hash array count = [0 for i in range(10)] x = i # creating a copy of i # initializing variables to compare lengths of digits count1 = 0 count2 = 0 # counting frequency of the digits while (x): count[x%10] += 1 x = int(x / 10) count1 += 1 # checking if each digit is present once for j in range(0,10,1): if (count[j] == 1): count2 += 1 if (count1 == count2): return i i -= 1 # Driver code if __name__ == '__main__': n = 8490 print(findNumber(n)) # This code is implemented by # Surendra_Gangwar
C#
// C# program to find a number less than
// n such that all its digits are distinct
using System;
class GFG
{
// Function to find a number less than
// n such that all its digits are distinct
static int findNumber(int n)
{
// looping through numbers less than n
for (int i = n - 1; i >= 0; i--)
{
// initializing a hash array
int[] count = new int[10];
int x = i; // creating a copy of i
// initializing variables to compare
// lengths of digits
int count1 = 0, count2 = 0;
// counting frequency of the digits
while (x > 0)
{
count[x % 10]++;
x /= 10;
count1++;
}
// checking if each digit is
// present once
for (int j = 0; j < 10; j++)
{
if (count[j] == 1)
count2++;
}
if (count1 == count2)
return i;
}
return -1;
}
// Driver code
static public void Main ()
{
int n = 8490;
Console.WriteLine(findNumber(n));
}
}
// This code is contributed by akt_mit
PHP
<?php
// PHP program to find a number less than
// n such that all its digits are distinct
// Function to find a number less than
// n such that all its digits are distinct
function findNumber($n)
{
// looping through numbers less than n
for ($i = $n - 1;$i >= 0 ; $i--)
{
// initializing a hash array
$count = array_fill(0, 10, 0);
$x = $i; // creating a copy of i
// initializing variables to
// compare lengths of digits
$count1 = 0; $count2 = 0;
// counting frequency of the digits
while ($x)
{
$count[$x % 10]++;
$x = (int)($x / 10);
$count1++;
}
// checking if each digit
// is present once
for ($j = 0; $j < 10; $j++)
{
if ($count[$j] == 1)
$count2++;
}
if ($count1 == $count2)
return $i;
}
}
// Driver code
$n = 8490;
echo findNumber($n);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program to find a number less than
// n such that all its digits are distinct
// Function to find a number less than
// n such that all its digits are distinct
function findNumber(n)
{
// looping through numbers less than n
for (i = n - 1;i >=0 ; i--) {
// initializing a hash array
var count=Array.from({length: 10}, (_, i) => 0);
var x = i; // creating a copy of i
// initializing variables to compare lengths of digits
var count1 = 0, count2 = 0;
// counting frequency of the digits
while (x>0) {
count[x % 10]++;
x = parseInt(x/10);
count1++;
}
// checking if each digit is present once
for (j = 0; j < 10; j++) {
if (count[j] == 1)
count2++;
}
if (count1 == count2)
return i;
}
return -1;
}
// Driver code
var n = 8490;
document.write(findNumber(n));
// This code is contributed by 29AjayKumar
</script>
Producción:
8479
Complejidad de tiempo: O (N * log 10 N) donde n es el número de elementos en una array dada. Como, estamos usando un ciclo para atravesar N veces, por lo que nos costará O (N) tiempo y estamos usando un ciclo while que costará O (logN) a medida que disminuimos por división de piso de 10 cada vez.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA