Es un problema muy bonito.
En pseudocódigo tu solución quedaría así:
INICIO
PEDIR numero
digitos[LONGITUD_MAXIMA] // array de longitud igual al maximo numero de digitos que puede tener el numero
numeroDigitos := calcularDigitos(numero, digitos)
...
FIN
La solución por
YreX-DwX parece correcta, pero un poco ineficaz, ya qu está en complejidad O(log^2(N)). A grandes rasgos, esto quiere decir que para un número de 10 cifras, hace 10*10 veces la operación más intern, para uno de 1000, hace 1000*1000 veces...
Yo propongo una solucion en O(log(N)), es decir , para un numero de 10 cifras, hace 10*10 veces la operación . Para uno de 1000, hace 1000*10 veces la operación interna...., Para uno de 4000 cifras, hace 4000*10 veces la operación interna... Y en espacio es O(10)=O(1), y que solo hay 10 digtos posibles...
/*
Title: Narcisist number (in base 10)
P : N == \sum i : 0 <= i <= log(N): a_i*10^i
Q : N==\sum i : 0 <= i <= log(N): a_i^{log(N)+1}
3 2 1 0
+-----+-----+-----+
| 1 | 5 | 3 | YES, since 153=1^3+5^3+3^3
+-----+-----+-----+
I ::= 0<=n<=log(N)+1 and Q[log(N)/n-1] and
M=N/10^n and
(n<=log(N) ->
(\forall i : 0 <= i < 10 : pow[i]=i^n and frec[i]=FREC(i,N%10^n)))
!B ::= n==log (N)+1
B ::= n<log (N)+1 ; // i.e. M>0
Init:
-----
n,pow[0..9],frec[0..9]=0,
|- P -> I [n/0,M/N,pow[0..9]=[1]^10, frec[0..9]=[0]^10]
QUOTE(N,n) = log (N)+1 - n >= 0 (Cuota decreases)
Step:
-----
n = n + 1 ; // i.e. M = M/10 ;
*/
#include <iostream>
#include <cassert>
using namespace std;
int narcisist(const unsigned long long N)
{
unsigned long long pow[10]={1,1,1,1,1,1,1,1,1,1} ; // [0-9]^0
unsigned long long frec[10]={0,0,0,0,0,0,0,0,0,0} ;
unsigned long long sum,M;
assert(N);
for (M=N ; M ;M/=10 ) // O(log(N)
{
frec[M%10]+=1;
int d;
for (sum=d=0 ; d<10 ;d++ ) // O(1)
{
pow[d]*=d;
sum+=pow[d]*frec[d];
}
}
// cout <<"trace " << N << " " << sum << endl;
return sum==N;
}
int main (int argc, char *args[])
{
unsigned long long N;
for( ; cin >> N ; )
cout << narcisist(N) << endl;
return 0;
}
Solo me se 153 y 1634 como numero narcisistas en base 10... SI alguien sabe otros, puede comprobar...
g++ narcisista.cc -o main && ./main
1634
1
153
1
154
0