Khó 0 đã giải Tỷ lệ chấp nhận 0%

Digit Factorial Chains

Count starting numbers whose digit factorial chain has exactly a given number of distinct terms.

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

  • Follow a chain until a value repeats
  • Find chain lengths inside and before a loop
  • Reuse stored lengths

Đề bài

Xem bản dịch

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ụ

Ví dụ 1
Đầ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.

Ví dụ 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.

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.