All challenges
Hard 0 solved 0% acceptance

Longest Recurring Cycle

Find the d up to a limit whose fraction 1/d has the longest repeating decimal block.

What you'll learn

  • Simulate long division with remainders
  • Detect a repeat with a lookup table
  • Find a cycle length from first positions

Problem

Some unit fractions end (1/4 = 0.25) and the rest repeat forever: 1/6 = 0.1666... repeats a block of 1 digit and 1/7 = 0.142857142857... a block of 6. Among d = 2, 3, ..., limit, find the d whose 1/d has the longest repeating block. Do the long division by hand in code: the digits start repeating as soon as a remainder comes back.

Implement longest_recurring_cycle(limit).

Input

limit: The largest denominator to try.

Output

Return the d with the longest repeating block. A fraction that ends has a block length of 0. If several d tie, return the smallest.

Constraints

2 ≤ limit ≤ 2000

Examples

Example 1
Input:
limit = 8

Expected output:
expected = 7
Input:
long long limit = 8;

Expected output:
long long expected = 7;
Input:
long limit = 8;

Expected output:
long expected = 7;

Explanation

Block lengths for 2 to 8 are 0, 1, 0, 0, 1, 6, 0, so the answer is 7.

Example 2
Input:
limit = 5

Expected output:
expected = 3
Input:
long long limit = 5;

Expected output:
long long expected = 3;
Input:
long limit = 5;

Expected output:
long expected = 3;

Explanation

1/3 repeats one digit, 1/2, 1/4 and 1/5 end, so the answer is 3.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Each new digit of 1/d comes from the remainder times 10.

Hint 2

Remember the step where each remainder first appeared.

Hint 3

If the remainder becomes 0 the decimal ends; otherwise the cycle length is the gap between two visits of the same remainder.

Expected complexity

O(limit²) time, O(limit) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.