Dado un número entero N , la tarea es encontrar todos los números autodescriptivos del 1 al N
Un número autodescriptivo es un entero n en la base dada b tiene una longitud de b dígitos en el que cada dígito en la posición p (el dígito más significativo está en la posición 0 y el menos significativo en la posición b – 1 ) cuenta cuántas veces un dígito p está en n .
Por ejemplo, en base 10, 6210001000 es un número autodescriptivo ya que hay seis 0, dos 1, un 2 y un 6.
Explicación:
es un número de 10 dígitos en base 10.
Tiene 6 en la posición 0 y hay seis 0 en 6210001000.
Tiene 2 en la posición 1 y hay dos 1 en 6210001000.
Tiene 1 en la posición 2 y hay un 2 en 6210001000.
Tiene 0 en la posición 3 y hay cero 3 en 6210001000.
Tiene 0 en la posición 4 y hay cero 4 en 6210001000.
Tiene 0 en la posición 5 y hay cero 5 en 6210001000.
Tiene 1 en la posición 6 y hay un 6 en 6210001000.
Tiene 0 en la posición 7 y hay cero 7 en 6210001000.
Tiene 0 en la posición 8 y hay cero 8 en 6210001000.
Tiene 0 en la posición 9 y hay cero 9 en 6210001000.
[Fuente: Wikipedia ]
Ejemplos:
Entrada: N = 10000
Salida: 1210 2020
Explicación: Del 1 al N solo estos dos números son los números autodescriptivosEntrada: N = 10
Salida:
Explicación: No hay un número autodescriptivo en el rango [1, 10]
Aquí hay un programa para imprimir todos los números autodescriptivos por debajo de 100000000. En el programa a continuación, acabamos de ignorar un hecho sobre el número autodescriptivo que debe tener tantos dígitos como la base se da.
Descripción del Programa :
1 . En primer lugar, todos los dígitos se extraen del ciclo externo y se almacenan en una variable b en cada iteración.
2 . Luego, en el ciclo interno hay un recuento de cuántas veces el número i (este i es el índice iésimo del ciclo externo) está presente en la string.
3 . Finalmente, esa cuenta se compara con el dígito presente en el i-ésimo índice almacenado en la variable b.
C++
// C++ program to print
// all self descriptive
// number below 100000000
#include <iostream>
using namespace std;
bool isSelfDescriptiveNumber(int num)
{
// converting the integer
// num to string
string s = to_string(num);
for (int i = 0;
i < s.size(); i++)
{
// Extracting each digit
// one by one from the
// string
char temp_char = s.at(i);
// converting the string
// (digit) into integer b
// variable stores the digit
// present at index 'i'
int b = temp_char - '0';
// counting how many
// times the particular
// digit occur in the
// whole number "num"
int count = 0;
for (int j = 0;
j < s.size(); j++)
{
// converting string
// char to integer
int temp = s.at(j) - '0';
// checking whether it is
// equal to the index 'i'
// if it is then increment
// the count .
if (temp == i)
{
count++;
}
}
// If it is not equal
// it return false .
if (count != b)
return false;
}
return true;
}
// Driver Code
int main()
{
int N = 1000000;
for (int i = 1; i <= N; i++)
if (isSelfDescriptiveNumber(i))
cout << i << endl;
return 0;
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Java
// Java program to print all self descriptive
// number below 100000000
public class SelfDescriptive {
public static boolean isSelfDescriptiveNumber(int num)
{
// converting the integer num to string
String s = Integer.toString(num);
for (int i = 0; i < s.length(); i++) {
// Extracting each digit one by one from the string
String temp_char = s.charAt(i) + "";
// converting the string (digit) into integer
// b variable stores the digit present at index 'i'
int b = Integer.parseInt(temp_char);
// counting how many times the particular digit
// occur in the whole number "num"
int count = 0;
for (int j = 0; j < s.length(); j++) {
// converting string char to integer
int temp = Integer.parseInt(s.charAt(j) + "");
// checking whether it is equal to the index 'i'
// if it is then increment the count .
if (temp == i) {
count++;
}
}
// If it is not equal
// it return false .
if (count != b)
return false;
}
return true;
}
public static void main(String[] args)
{
int N = 1000000;
for (int i = 1; i <= N; i++)
if (isSelfDescriptiveNumber(i))
System.out.println(i);
}
}
Python3
# Python3 program to print
# all self descriptive
# number below 100000000
def isSelfDescriptiveNumber(num):
# Converting the integer
# num to string
s = str(num)
for i in range(len(s)):
# Extracting each digit
# one by one from the
# string
temp_char = s[i]
# Converting the string
# (digit) into integer b
# variable stores the digit
# present at index 'i'
b = ord(temp_char) - ord('0')
# Counting how many
# times the particular
# digit occur in the
# whole number "num"
count = 0
for j in range(len(s)):
# Converting string
# char to integer
temp = ord(s[j]) - ord('0')
# Checking whether it is
# equal to the index 'i'
# if it is then increment
# the count .
if (temp == i):
count += 1
# If it is not equal
# it return false .
if (count != b):
return False
return True
# Driver code
if __name__=="__main__":
N = 1000000
for i in range(1, N+1):
if (isSelfDescriptiveNumber(i)):
print(i)
# This code is contributed by rutvik_56
C#
// C# program to print
// all self descriptive
// number below 100000000
using System;
class GFG {
static bool isSelfDescriptiveNumber(int num)
{
// converting the integer
// num to string
string s = num.ToString();
for (int i = 0; i < s.Length; i++) {
// Extracting each digit
// one by one from the
// string
string temp_char = s[i] + "";
// converting the string
// (digit) into integer b
// variable stores the digit
// present at index 'i'
int b = int.Parse(temp_char);
// counting how many
// times the particular
// digit occur in the
// whole number "num"
int count = 0;
for (int j = 0; j < s.Length; j++) {
// converting string
// char to integer
int temp = int.Parse(s[j] + "");
// checking whether it is
// equal to the index 'i'
// if it is then increment
// the count .
if (temp == i) {
count++;
}
}
// If it is not equal
// it return false .
if (count != b)
return false;
}
return true;
}
// Driver Code
static void Main()
{
int N = 1000000;
for (int i = 0; i < N; i++)
if (isSelfDescriptiveNumber(i))
Console.WriteLine(i);
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
PHP
<?php
// PHP program to print
// all self descriptive
// number below 100000000
// Note:
// 100000000 is a huge no so
// it give sometime TLE error
// because its takes compile
// time above 5 sec
function isSelfDescriptiveNumber($num)
{
// converting the integer
// num to string
$s = strval($num);
for ($i = 0; $i < strlen($s); $i++)
{
// Extracting each digit
// one by one from the
// string
$temp_char = $s[$i];
// converting the string
// (digit) into integer b
// variable stores the digit
// present at index 'i'
$b = $temp_char - '0';
// counting how many
// times the particular
// digit occur in the
// whole number "num"
$count = 0;
for ($j = 0; $j < strlen($s); $j++)
{
// converting string
// char to integer
$temp = $s[$j] - '0';
// checking whether it is
// equal to the index 'i'
// if it is then increment
// the count .
if ($temp == $i)
{
$count++;
}
}
// If it is not equal
// it return false .
if ($count != $b)
return false;
}
return true;
}
// Driver Code
$N = 1000000;
for ($i = 0; $i <= $N; $i++)
if (isSelfDescriptiveNumber($i))
echo $i."\n";
// This code is contributed
// by mits
?>
Javascript
// JavaScript program to print
// all self descriptive
// number below 100000000
function isSelfDescriptiveNumber(num)
{
// converting the integer
// num to string
let s = num.toString();
for (let i = 0;
i < s.length; i++)
{
// Extracting each digit
// one by one from the
// string
let temp_char = s[i];
// converting the string
// (digit) into integer b
// variable stores the digit
// present at index 'i'
let b = temp_char - '0';
// counting how many
// times the particular
// digit occur in the
// whole number "num"
let count = 0;
for (let j = 0; j < s.length; j++)
{
// converting string
// char to integer
let temp = s[j] - '0';
// checking whether it is
// equal to the index 'i'
// if it is then increment
// the count .
if (temp == i)
{
count++;
}
}
// If it is not equal
// it return false .
if (count != b)
return false;
}
return true;
}
// Driver Code
let N = 1000000;
for (let i = 1; i <= N; i++)
if (isSelfDescriptiveNumber(i))
console.log(i);
// This code is contributed by Nidhi goel
1210 2020 21200
Complejidad de tiempo: O( N*len(N)*len(N) )
Espacio auxiliar: O(1)
Enfoque eficiente: el tiempo en el enfoque anterior se puede reducir almacenando la frecuencia de cada dígito en una array de 10 longitudes y luego verificándola consecutivamente con el dígito correspondiente.
C++14
#include <bits/stdc++.h>
using namespace std;
bool isSelfDescriptiveNumber(int num)
{
string str=to_string(num);
int i;
int freq[10]={0};
while(num>0)
{
freq[num%10]++;
num/=10;
}
for(i=0;i<str.length();i++)
if(freq[i]!=str[i]-'0')
return 0;
return 1;
}
int main()
{
int N = 1000000;
for (int i = 1; i <= N; i++)
if (isSelfDescriptiveNumber(i))
cout << i << endl;
return 0;
}
Python3
# Python3 code to implement the approach # Function to check if the number is self descriptive def isSelfDescriptiveNumber(num): str_ = str(num) # A frequency table for all the digits freq = [0 for _ in range(10)] # Building the frequency table for the number while (num > 0): freq[num % 10] += 1 num //= 10 for i in range(len(str_)): if (freq[i] != int(str_[i])): return 0 return 1 # Driver Code N = 1000000 for i in range(1, 1 + N): if (isSelfDescriptiveNumber(i)): print(i) # This code is contributed by phasing17
Javascript
// JavaScript code to implement the approach
function isSelfDescriptiveNumber(num)
{
let str = num.toString();
let i;
let freq = new Array(10).fill(0);
while (num > 0) {
freq[num % 10]++;
num = Math.floor(num / 10);
}
for (i = 0; i < str.length; i++)
if (freq[i] != parseInt(str[i]))
return 0;
return 1;
}
let N = 1000000;
for (var i = 1; i <= N; i++)
if (isSelfDescriptiveNumber(i))
console.log(i);
// This code is contributed by phasing17
1210 2020 21200
Complejidad de Tiempo: O( N*len(N) )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA