Tất cả thử thách
Khó 0 đã giải Tỷ lệ chấp nhận 0%

Longest Recurring Cycle

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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.

Ràng buộc

2 ≤ limit ≤ 2000

Ví dụ

Ví dụ 1
Đầu vào:
limit = 8

Kết quả mong đợi:
expected = 7
Đầu vào:
long long limit = 8;

Kết quả mong đợi:
long long expected = 7;
Đầu vào:
long limit = 8;

Kết quả mong đợi:
long expected = 7;

Giải thích

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

Ví dụ 2
Đầu vào:
limit = 5

Kết quả mong đợi:
expected = 3
Đầu vào:
long long limit = 5;

Kết quả mong đợi:
long long expected = 3;
Đầu vào:
long limit = 5;

Kết quả mong đợi:
long expected = 3;

Giải thích

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

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 2

Remember the step where each remainder first appeared.

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.