Problem 39.7 · Math for Coding InterviewsMedium

Count Good Numbers

What it teaches: Fast modular exponentiation for counts with huge n.

Practise it on judges as “Count Good Numbers”.

In plain words

Build a digit string slot by slot. Even slots (0, 2, 4, …) can hold 5 choices (0, 2, 4, 6, 8); odd slots can hold 4 choices (2, 3, 5, 7). Multiply the choices: 5 to the power of the even slots times 4 to the power of the odd slots. n can be huge, so compute powers by repeated squaring.

Return the count modulo 10⁹ + 7. Example: n = 4 → 400.

The problem

A digit string is good if digits at even indices are even (0, 2, 4, 6, 8) and digits at odd indices are prime (2, 3, 5, 7). Return the number of good strings of length n, modulo 10⁹ + 7.

Example 1

Input: n = 4
Output: 400

Constraints

1 ≤ n ≤ 10¹⁵

Pattern clues in the wording

→ Independent choices per position
→ n up to 10¹⁵
→ Answer modulo 10⁹ + 7

These clues point to Number Theory and Combinatorics: GCD, primes, modular arithmetic, fast power and counting formulas that turn loops into a few lines of math.

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public int countGoodNumbers(long n) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	n = 1	5
2	n = 4	400
3	n = 50	564908303

From slow to fast

Approaches

1. Fast power · O(log n)

Fast power

Time O(log n) Space O(1)

power(5, (n + 1) / 2) × power(4, n / 2) mod p.

▶ Dry run: 5^even × 4^odd with fast powern = 4

slots(vars)

even slots: (4 + 1) / 2 = 2odd slots: 4 / 2 = 2

Step 1/4Slots 0 and 2 have 5 choices each; slots 1 and 3 have 4 each.

Approach 1

class Solution {
    private static final long P = 1_000_000_007L;

    public int countGoodNumbers(long n) {
        return (int) (power(5, (n + 1) / 2) * power(4, n / 2) % P);
    }

    private long power(long b, long e) {
        long r = 1;
        b %= P;
        while (e > 0) {
            if ((e & 1) == 1) r = r * b % P;
            b = b * b % P;
            e >>= 1;
        }
        return r;
    }
}

Verdict: A loop over n is impossible here.

Before you submit

Edge cases and common mistakes

Test these inputs

n = 1 (5)
n odd vs even

Mistakes people make

Math.pow with doubles (loses precision).

Interview

Follow-up questions

Why reduce b before squaring?

Command Palette

The problem

Approaches

Fast power

Edge cases and common mistakes

Follow-up questions