Count Good Numbers

Medium
1313.

Count Good Numbers

Count Good Numbers is a medium coding problem on math and recursion, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var countGoodNumbers = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Good Numbers — Solution in Python, Java & C++

Count Good Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on math and recursion.

Count Good Numbers is a medium coding problem on math and recursion, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Math, Recursion
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Count Good Numbers

  1. Hint 1

    Positions are independent: each even index has 5 choices, each odd index has 4.

  2. Hint 2

    There are ceil(n / 2) even indices and floor(n / 2) odd ones, so the count is 5^ceil(n/2) · 4^floor(n/2).

  3. Hint 3

    The exponents reach 10^9 — use fast exponentiation by squaring, reducing modulo 10^9 + 7 after every multiplication.

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

Java

public static int countGoodNumbers(int n) {
    long even = ((long) n + 1) / 2, odd = n / 2;
    return (int) (goodPow(5, even) * goodPow(4, odd) % 1000000007L);
}

private static long goodPow(long b, long e) {
    final long MOD = 1000000007L;
    long r = 1;
    b %= MOD;
    while (e > 0) {
        if ((e & 1) == 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return r;
}

C++

long long goodPow(long long b, long long e) {
    const long long MOD = 1000000007LL;
    long long r = 1;
    b %= MOD;
    while (e > 0) {
        if (e & 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return r;
}

int countGoodNumbers(int n) {
    long long even = ((long long) n + 1) / 2, odd = n / 2;
    return (int) (goodPow(5, even) * goodPow(4, odd) % 1000000007LL);
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Recursion