Problema
Alcune frazioni unitarie hanno uno sviluppo decimale finito (1/4 = 0,25), le altre sono periodiche: 1/6 = 0,1666... ha un periodo di 1 cifra e 1/7 = 0,142857142857... un periodo di 6 cifre. Tra d = 2, 3, ..., limit, trova il d per cui 1/d ha il periodo più lungo. Esegui la divisione in colonna nel codice: le cifre iniziano a ripetersi non appena ricompare un resto già visto.
Implementa longest_recurring_cycle(limit).
Input
limit: il denominatore più grande da provare.
Output
Restituisci il d con il periodo più lungo. Una frazione con sviluppo finito ha un periodo di lunghezza 0. In caso di parità, restituisci il d più piccolo.
Vincoli
2 ≤ limit ≤ 2000
Esempi
Input:
limit = 8
Output atteso:
expected = 7
Input:
long long limit = 8;
Output atteso:
long long expected = 7;
Input:
long limit = 8;
Output atteso:
long expected = 7;
Spiegazione
Da 2 a 8 le lunghezze dei periodi sono 0, 1, 0, 0, 1, 6, 0, quindi la risposta è 7.
Input:
limit = 5
Output atteso:
expected = 3
Input:
long long limit = 5;
Output atteso:
long long expected = 3;
Input:
long limit = 5;
Output atteso:
long expected = 3;
Spiegazione
1/3 ha un periodo di una cifra, mentre 1/2, 1/4 e 1/5 hanno uno sviluppo finito, quindi la risposta è 3.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Ogni nuova cifra di 1/d si ottiene dal resto moltiplicato per 10.
Suggerimento 2
Ricorda a quale passo è comparso per la prima volta ogni resto.
Suggerimento 3
Se il resto diventa 0 lo sviluppo decimale è finito; altrimenti la lunghezza del periodo è la distanza tra due comparse dello stesso resto.
Complessità attesa
tempo O(limit²), spazio aggiuntivo O(limit)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.