Tutte le sfide
Difficile 0 risolte 0% di accettazione

Periodo decimale più lungo

Trova il d, fino a un limite, per cui la frazione 1/d ha il periodo decimale più lungo.

Cosa imparerai

  • Simulare la divisione in colonna con i resti
  • Riconoscere una ripetizione con una tabella di lookup
  • Ricavare la lunghezza del ciclo dalle prime posizioni

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

Esempio 1
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.

Esempio 2
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.

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.