Đề bài
Replace a number by the sum of the factorials of its digits: 145 gives 1! + 4! + 5! = 145 again, and 69 gives 6! + 9! = 363600. Repeating this always falls into a loop. The chain of a start is its terms until the first repeat: 69, 363600, 1454, 169, 363601 and then 1454 again, so 69 has 5 distinct terms. Count the starting numbers from 1 to limit whose chain has exactly length distinct terms.
Implement digit_factorial_chains(limit, length).
Many chains run into the same numbers. Store each number's chain length once it is known and reuse it.
Input
limit: The largest starting number.
length: The number of distinct terms wanted, the start included.
Output
Return how many starting numbers n with 1 ≤ n ≤ limit have exactly length distinct terms in their chain.
Ràng buộc
1 ≤ limit ≤ 100,000; 1 ≤ length ≤ 70
Ví dụ
Đầu vào:
limit = 2
length = 1
Kết quả mong đợi:
expected = 2
Đầu vào:
long long limit = 2;
long long length = 1;
Kết quả mong đợi:
long long expected = 2;
Đầu vào:
long limit = 2;
long length = 1;
Kết quả mong đợi:
long expected = 2;
Giải thích
1! = 1 and 2! = 2, so 1 and 2 each map to themselves and have a chain of 1 term. The answer is 2.
Đầu vào:
limit = 10
length = 2
Kết quả mong đợi:
expected = 1
Đầu vào:
long long limit = 10;
long long length = 2;
Kết quả mong đợi:
long long expected = 1;
Đầu vào:
long limit = 10;
long length = 2;
Kết quả mong đợi:
long expected = 1;
Giải thích
3 gives 6, then 720, 5043, ... so it is long. 10 gives 1! + 0! = 2 and then 2 again: two terms. Only 10 has exactly 2, so the answer is 1.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Precompute 0! to 9! once.
Gợi ý 2
Record each value's step number in the current chain; a repeat tells you where the loop starts.
Gợi ý 3
Values in the loop all have the loop's length, and each value before it has one more than the next.
Độ phức tạp mong đợi
O(limit × log limit) time with memoization, 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.