Todos os desafios
Difícil 0 resolvidos 0% de aceitação

Maior período de dízima periódica

Encontre, até um limite, o d cuja fração 1/d tem o maior período decimal.

O que você vai aprender

  • Simular a divisão longa com os restos
  • Detectar uma repetição com uma tabela de consulta
  • Calcular o tamanho do ciclo a partir das primeiras posições

Problema

Ver original (inglês)

Algumas frações unitárias são decimais exatos (1/4 = 0,25) e as demais são dízimas periódicas: 1/6 = 0,1666... repete um bloco de 1 dígito e 1/7 = 0,142857142857... um bloco de 6. Entre d = 2, 3, ..., limit, encontre o d cujo 1/d tem o maior bloco repetido (o período). Faça a divisão longa no código, como no papel: os dígitos começam a se repetir assim que um resto volta a aparecer.

Implemente longest_recurring_cycle(limit).

Entrada

limit: o maior denominador a testar.

Saída

Retorne o d com o maior período. Uma fração com decimal exato tem período 0. Em caso de empate, retorne o menor d.

Restrições

2 ≤ limit ≤ 2000

Exemplos

Exemplo 1
Entrada:
limit = 8

Saída esperada:
expected = 7
Entrada:
long long limit = 8;

Saída esperada:
long long expected = 7;
Entrada:
long limit = 8;

Saída esperada:
long expected = 7;

Explicação

Os períodos de 2 a 8 são 0, 1, 0, 0, 1, 6, 0, então a resposta é 7.

Exemplo 2
Entrada:
limit = 5

Saída esperada:
expected = 3
Entrada:
long long limit = 5;

Saída esperada:
long long expected = 3;
Entrada:
long limit = 5;

Saída esperada:
long expected = 3;

Explicação

1/3 repete um dígito, enquanto 1/2, 1/4 e 1/5 são exatos, então a resposta é 3.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Cada novo dígito de 1/d sai do resto multiplicado por 10.

Dica 2

Guarde o passo em que cada resto apareceu pela primeira vez.

Dica 3

Se o resto virar 0, o decimal é exato; caso contrário, o período é a distância entre duas aparições do mesmo resto.

Complexidade esperada

tempo O(limit²), espaço extra O(limit)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.