Tutte le sfide
Difficile 0 risolte 0% di accettazione

Catene di fattoriali delle cifre

Conta i numeri di partenza la cui catena di fattoriali delle cifre ha esattamente un certo numero di termini distinti.

Cosa imparerai

  • Seguire una catena finché un valore si ripete
  • Trovare le lunghezze delle catene dentro e prima di un ciclo
  • Riutilizzare le lunghezze memorizzate

Problema

Sostituisci un numero con la somma dei fattoriali delle sue cifre: 145 dà 1! + 4! + 5! = 145, di nuovo lui, e 69 dà 6! + 9! = 363600. Ripetendo il procedimento si finisce sempre in un ciclo. La catena di un numero di partenza è formata dai suoi termini fino alla prima ripetizione: 69, 363600, 1454, 169, 363601 e poi di nuovo 1454, quindi 69 ha 5 termini distinti. Conta i numeri di partenza da 1 a limit la cui catena ha esattamente length termini distinti.

Implementa digit_factorial_chains(limit, length).

Molte catene passano per gli stessi numeri. Memorizza la lunghezza della catena di ogni numero appena la conosci e riutilizzala.

Input

limit: il numero di partenza più grande.

length: il numero di termini distinti richiesto, compreso quello di partenza.

Output

Restituisci quanti numeri di partenza n con 1 ≤ n ≤ limit hanno esattamente length termini distinti nella loro catena.

Vincoli

1 ≤ limit ≤ 100 000; 1 ≤ length ≤ 70

Esempi

Esempio 1
Input:
limit = 2
length = 1

Output atteso:
expected = 2
Input:
long long limit = 2;
long long length = 1;

Output atteso:
long long expected = 2;
Input:
long limit = 2;
long length = 1;

Output atteso:
long expected = 2;

Spiegazione

1! = 1 e 2! = 2, quindi 1 e 2 portano ciascuno a se stesso e hanno una catena di 1 termine. La risposta è 2.

Esempio 2
Input:
limit = 10
length = 2

Output atteso:
expected = 1
Input:
long long limit = 10;
long long length = 2;

Output atteso:
long long expected = 1;
Input:
long limit = 10;
long length = 2;

Output atteso:
long expected = 1;

Spiegazione

3 dà 6, poi 720, 5043, ..., quindi la sua catena è lunga. 10 dà 1! + 0! = 2 e poi di nuovo 2: due termini. Solo 10 ne ha esattamente 2, quindi la risposta è 1.

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Precalcola una volta sola i fattoriali da 0! a 9!.

Suggerimento 2

Registra il numero di passo di ogni valore nella catena corrente; una ripetizione ti dice dove inizia il ciclo.

Suggerimento 3

I valori nel ciclo hanno tutti la lunghezza del ciclo, e ogni valore prima del ciclo ha uno in più del successivo.

Complessità attesa

tempo O(limit × log limit) con la memoizzazione, spazio aggiuntivo O(limit)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.