Count Good Numbers — Medium Problem & Solution

Problem statement

A digit string (leading zeros allowed) is good when every digit at an even index (0-indexed) is even — 0, 2, 4, 6 or 8 — and every digit at an odd index is a prime — 2, 3, 5 or 7.

For example, "2582" is good, while "3245" is not (index 0 holds 3, which is odd).

Return how many good digit strings of length n exist, modulo 10^9 + 7. (Here n fits in a 32-bit integer; the original problem allows lengths up to 10^15.)

Example 1

Input: n = 1
Output: 5
Explanation: "0", "2", "4", "6" and "8".

Example 2

Input: n = 4
Output: 400
Explanation: Two even positions with 5 choices and two odd positions with 4 choices: 5·4·5·4.

Example 3

Input: n = 50
Output: 564908303

Constraints

• 1 <= n <= 2 * 10^9

How to solve Count Good Numbers

The choice at each position is independent of every other, so the count is a product of powers, computed with binary exponentiation.

Approach

1. Let even = (n + 1) / 2 and odd = n / 2 (integer division).
2. Compute 5^even mod M and 4^odd mod M by repeated squaring: square the base each round and multiply it into the result when the current exponent bit is 1.
3. Return their product modulo M = 10^9 + 7.

Why it works

A good string is exactly a choice of an even digit for each of the ceil(n/2) even indices and a prime digit for each of the floor(n/2) odd indices, and every combination gives a distinct string — the multiplication principle gives 5^even · 4^odd. Repeated squaring uses b^e = (b²)^(e/2) (times b when e is odd), so it needs only O(log n) multiplications, and reducing after each keeps every value below M.

Complexity

• Time — O(log n)
• Space — O(1)

Pitfalls

• Two residues below 10^9 + 7 multiply to ~10^18: use 64-bit integers, and in JavaScript split the multiplication (or the product loses precision past 2^53).
• Index 0 is even: an odd n has one more even position than odd ones.
• A loop that multiplies n times is far too slow for n = 2·10^9.

Reference solution

Python

def countGoodNumbers(n: int) -> int:
    MOD = 10 ** 9 + 7
    return pow(5, (n + 1) // 2, MOD) * pow(4, n // 2, MOD) % MOD

JavaScript

var countGoodNumbers = function(n) {
    var MOD = 1000000007;
    var mulMod = function(a, b) {
        var hi = Math.floor(b / 65536), lo = b % 65536;
        return ((a * hi) % MOD * 65536 + a * lo) % MOD;
    };
    var powMod = function(b, e) {
        var r = 1;
        b %= MOD;
        while (e > 0) {
            if (e % 2 === 1) r = mulMod(r, b);
            b = mulMod(b, b);
            e = Math.floor(e / 2);
        }
        return r;
    };
    return mulMod(powMod(5, Math.floor((n + 1) / 2)), powMod(4, Math.floor(n / 2)));
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Ways to Split Array Into Good Subarrays Medium
• Guess Number Higher or Lower II Medium
• Minimum Cost to Set Cooking Time Medium
• Broken Calculator Medium
• Construct the Longest New String Medium
• Minimum Cost to Make Array Equalindromic Medium