Generated by Codex with GPT-5

Quick facts

Problem gist

The problem asks for the number of length-n digit strings that satisfy two position rules:

  • Digits at even indices can be one of 0, 2, 4, 6, or 8.
  • Digits at odd indices can be one of 2, 3, 5, or 7.

Indices are zero-based, so index 0 is even. The string can start with 0; this is a digit string, not a normal integer representation. Because the answer can be enormous, return it modulo 1_000_000_007.

Core idea

Every position is independent. Once the index parity is known, the digit choice at that position does not affect any other position.

That means the answer is just a product of choices:

  • every even index contributes 5 possible digits;
  • every odd index contributes 4 possible digits.

For a length n string, the number of even indices is (n + 1) // 2. The number of odd indices is n // 2. The answer is:

5^((n + 1) // 2) * 4^(n // 2) mod 1_000_000_007

The only real implementation detail is exponentiation. Since n can be very large, multiplying 5 or 4 one step at a time is too slow. Use binary exponentiation, also called fast power, to compute each power in O(log n) time.

How to derive it

Start with a few small lengths.

For n = 1, only index 0 exists. It is even, so there are 5 strings.

For n = 2, index 0 has 5 choices and index 1 has 4 choices, so there are 5 * 4 = 20 strings.

For n = 3, the positions are even, odd, even. That gives 5 * 4 * 5 = 100 strings.

The pattern is not about the actual previous digit. It is only about how many even and odd positions exist. When n is odd, there is one more even position than odd position because index 0 starts the count. When n is even, the counts are equal.

Modulo arithmetic is safe throughout the multiplication because:

(a * b) mod M == ((a mod M) * (b mod M)) mod M

So the fast-power helper can reduce after every multiplication and keep all intermediate values small.

Python solution

from typing import Final


MODULUS: Final[int] = 1_000_000_007
EVEN_DIGIT_CHOICES: Final[int] = 5
PRIME_DIGIT_CHOICES: Final[int] = 4


class Solution:
    def countGoodNumbers(self, n: int) -> int:
        even_index_count = (n + 1) // 2
        odd_index_count = n // 2

        even_position_count = self._modular_power(
            EVEN_DIGIT_CHOICES,
            even_index_count,
        )
        odd_position_count = self._modular_power(
            PRIME_DIGIT_CHOICES,
            odd_index_count,
        )

        return (even_position_count * odd_position_count) % MODULUS

    def _modular_power(self, base: int, exponent: int) -> int:
        result = 1
        current_power = base % MODULUS

        # Binary exponentiation: use each bit of the exponent once.
        while exponent > 0:
            if exponent & 1:
                result = (result * current_power) % MODULUS

            current_power = (current_power * current_power) % MODULUS
            exponent >>= 1

        return result

The time complexity is O(log n) because each fast-power call halves the exponent at every step. The space complexity is O(1).

Interview follow-ups

Could this use Python’s built-in pow?

Yes. Python’s three-argument pow(base, exponent, modulus) performs efficient modular exponentiation. The same solution can be written as pow(5, (n + 1) // 2, MODULUS) * pow(4, n // 2, MODULUS) % MODULUS.

That version is shorter and production-friendly in normal Python code. In an interview, writing the helper by hand is often useful because it shows that the candidate understands why the solution is logarithmic instead of linear.

What if n were provided as a very large decimal string?

The direct formula still works, but the exponents could no longer be stored as normal integers. Because the modulus 1_000_000_007 is prime and both bases 4 and 5 are coprime with it, Fermat’s little theorem allows reducing exponents modulo 1_000_000_006.

The main extra work would be parsing the decimal string to compute floor(n / 2), ceil(n / 2), and each exponent modulo MODULUS - 1. That keeps the same mathematical formula, but changes the input-handling layer. The tradeoff is more implementation complexity for support beyond the original constraints.

What if even and odd positions had different allowed digit sets?

The formula generalizes directly. If even positions had a choices and odd positions had b choices, the answer would be a^ceil(n / 2) * b^floor(n / 2) modulo the required modulus.

This works for the same reason as the original problem: positions are independent. The only values that matter are the number of positions in each group and the number of valid choices for that group.

What if adjacent digits could not be equal?

Then the independence breaks. The choice at one position would constrain the next position, so simple multiplication by fixed counts would overcount invalid strings.

A practical approach would use dynamic programming over position parity and previous digit. Since there are only ten possible previous digits, the state remains small. The complexity would become O(n * 10 * 10) for direct transitions, or better with precomputed transition counts, but it would no longer be O(log n) unless matrix exponentiation were used.

Why does binary exponentiation work?

Binary exponentiation uses the binary representation of the exponent. For example, instead of multiplying by 5 thirteen times, it uses powers like 5^1, 5^2, 5^4, and 5^8, then multiplies only the powers whose bits appear in the exponent.

Each loop squares the current power and shifts the exponent right by one bit. That is why the number of iterations grows with the number of bits in n, not with n itself. The modulo operation after every multiplication preserves the final answer while preventing huge intermediate numbers.