Count Good Numbers

문제 설명

• Good Digit String이란, 다음 조건을 만족하는 문자열입니다.
  • 문자열은 숫자(0~9)로만 구성되어 있습니다.
  • 문자열의 앞자리에 0이 와도 됩니다.
  • 짝수 인덱스에 있는 숫자는 짝수이어야 합니다.
  • 홀수 인덱스에 있는 숫자는 소수이어야 합니다.
• 정수 n이 주어집니다.
• 길이 n의 Good Digit String의 총 개수를 반환해야 합니다.
  • 결과는 $10^9 + 7$로 나눈 나머지를 반환해야 합니다.

문제 풀이

Fast Exponentiation

• 자릿수별로 가능한 숫자의 개수를 곱해서 전체 경우의 수를 구합니다.
  • 짝수 인덱스 자리(0, 2, 4, ...): 가능한 숫자 = 5개 (0, 2, 4, 6, 8)
  • 홀수 인덱스 자리(1, 3, 5, ...): 가능한 숫자 = 4개 (2, 3, 5, 7)
• 전체 경우의 수 = 5^(짝수자리 수) * 4^(홀수자리 수)
  • 주어진 n이 최대 $10^{15}$이므로, 빠른 거듭제곱(Exponentiation by Squaring)을 사용합니다.
  • 또한, 거듭제곱 수가 매우 커질 수 있으므로, 모듈러 연산과 BigInt를 사용합니다.

export function countGoodNumbers(n: number): number {
  const MOD = BigInt(10 ** 9 + 7);
 
  function pow(x: bigint, y: bigint): bigint {
    let result = 1n;
    let [base, exponent] = [x, y];
    while (exponent > 0) {
      if (exponent % 2n === 1n) {
        result = (result * base) % MOD;
      }
      base = (base * base) % MOD;
      exponent = exponent / 2n;
    }
    return result;
  }
 
  const even = BigInt(Math.floor((n + 1) / 2));
  const odd = BigInt(Math.floor(n / 2));
  return Number((pow(5n, even) * pow(4n, odd)) % MOD);
}

복잡도

• 시간 복잡도: $O(log_2 n)$
• 공간 복잡도: $O(1)$