모든 챌린지
어려움 0명 해결 정답률 0%

Digit Factorial Chains

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

배우게 될 내용

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

문제

번역본 보기

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.

제약 조건

1 ≤ limit ≤ 100,000; 1 ≤ length ≤ 70

예시

예시 1
입력:
limit = 2
length = 1

예상 출력:
expected = 2
입력:
long long limit = 2;
long long length = 1;

예상 출력:
long long expected = 2;
입력:
long limit = 2;
long length = 1;

예상 출력:
long expected = 2;

설명

1! = 1 and 2! = 2, so 1 and 2 each map to themselves and have a chain of 1 term. The answer is 2.

예시 2
입력:
limit = 10
length = 2

예상 출력:
expected = 1
입력:
long long limit = 10;
long long length = 2;

예상 출력:
long long expected = 1;
입력:
long limit = 10;
long length = 2;

예상 출력:
long expected = 1;

설명

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.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

Precompute 0! to 9! once.

힌트 2

Record each value's step number in the current chain; a repeat tells you where the loop starts.

힌트 3

Values in the loop all have the loop's length, and each value before it has one more than the next.

예상 복잡도

O(limit × log limit) time with memoization, O(limit) extra space

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.