Count Good Numbers

medium math recursion fast power

Problem

A length-n digit string is good when every digit at an even index (0-indexed) is even (one of 0,2,4,6,8 → 5 choices) and every digit at an odd index is prime (one of 2,3,5,7 → 4 choices). Count all good strings of length n modulo 10⁹+7. Since n can reach 10¹⁵, the count is 5^⌈n/2⌉ · 4^⌊n/2⌋ computed with fast exponentiation.

Inputn = 4

Output400

Indices 0 and 2 are even (5 choices each), indices 1 and 3 are odd (4 choices each): 5 · 4 · 5 · 4 = 400.

n (length of the digit string)

def countGoodNumbers(n):
    MOD = 10**9 + 7

    def power(base, exp):           # fast modular exponentiation
        base %= MOD
        result = 1
        while exp > 0:
            if exp & 1:             # current bit set: fold base in
                result = result * base % MOD
            base = base * base % MOD # square the base
            exp >>= 1               # drop the lowest bit
        return result

    even_slots = (n + 1) // 2       # indices 0,2,4,... -> 5 choices
    odd_slots = n // 2              # indices 1,3,5,... -> 4 choices
    return power(5, even_slots) * power(4, odd_slots) % MOD

function countGoodNumbers(n) {
  const MOD = 1000000007n;

  function power(base, exp) {        // fast modular exponentiation
    base %= MOD;
    let result = 1n;
    while (exp > 0n) {
      if (exp & 1n)                  // current bit set: fold base in
        result = result * base % MOD;
      base = base * base % MOD;       // square the base
      exp >>= 1n;                    // drop the lowest bit
    }
    return result;
  }

  const evenSlots = (n + 1n) / 2n;   // indices 0,2,4,... -> 5 choices
  const oddSlots = n / 2n;           // indices 1,3,5,... -> 4 choices
  return Number(power(5n, evenSlots) * power(4n, oddSlots) % MOD);
}

int countGoodNumbers(long n) {
    long MOD = 1_000_000_007L;

    long evenSlots = (n + 1) / 2;    // indices 0,2,4,... -> 5 choices
    long oddSlots = n / 2;           // indices 1,3,5,... -> 4 choices
    return (int) (power(5, evenSlots, MOD) * power(4, oddSlots, MOD) % MOD);
}

long power(long base, long exp, long MOD) {  // fast modular exponentiation
    base %= MOD;
    long result = 1;
    while (exp > 0) {
        if ((exp & 1) == 1)          // current bit set: fold base in
            result = result * base % MOD;
        base = base * base % MOD;     // square the base
        exp >>= 1;                   // drop the lowest bit
    }
    return result;
}

long long power(long long base, long long exp, long long MOD) {
    base %= MOD;
    long long result = 1;
    while (exp > 0) {
        if (exp & 1)                 // current bit set: fold base in
            result = result * base % MOD;
        base = base * base % MOD;     // square the base
        exp >>= 1;                   // drop the lowest bit
    }
    return result;
}

int countGoodNumbers(long long n) {
    long long MOD = 1e9 + 7;
    long long evenSlots = (n + 1) / 2;   // indices 0,2,... -> 5 choices
    long long oddSlots = n / 2;          // indices 1,3,... -> 4 choices
    return (int)(power(5, evenSlots, MOD) * power(4, oddSlots, MOD) % MOD);
}

Explanation

Each position of the string is chosen independently, so by the multiplication rule the total count is just the product of the number of choices at every index.

Even indices 0, 2, 4, … accept an even digit: 0, 2, 4, 6, 8 — 5 choices. Odd indices 1, 3, 5, … accept a prime digit: 2, 3, 5, 7 — 4 choices. A length-n string has ⌈n/2⌉ = (n+1)/2 even positions and ⌊n/2⌋ = n/2 odd positions, so the answer is 5^(n+1)/2 · 4^n/2.

Because n may be as large as 10¹⁵, multiplying that many times is impossible. We use binary (fast) exponentiation: to compute base^exp we walk the bits of exp from low to high. We keep squaring base (giving base, base², base⁴, …) and, whenever the current bit of exp is 1, we fold the current squared value into the running result. This finishes in O(log exp) multiplications.

Every multiplication is taken modulo 10⁹+7 to keep numbers small and to return the answer in the required form. The visualization shows the bits of the exponent being consumed one at a time while base squares and result accumulates.

For n = 4: even slots = 2, odd slots = 2, so the answer is 5² · 4² = 25 · 16 = 400.

Time: O(log n) Space: O(1)