Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Count Good Numbers

MEDIUMProblemSolveExternal Links

Description

You are given a positive integer n representing the length of a digit string. A digit string is called good if it satisfies two rules:

  1. Every digit at an even index (0, 2, 4, ...) must be an even digit — one of {0, 2, 4, 6, 8}.
  2. Every digit at an odd index (1, 3, 5, ...) must be a prime digit — one of {2, 3, 5, 7}.

Indices are 0-based, meaning the first character is at index 0, the second at index 1, and so on.

For instance, the string "2582" is good: index 0 has 2 (even), index 1 has 5 (prime), index 2 has 8 (even), index 3 has 2 (prime). The string "3245" is not good because index 0 has 3, which is odd — not an even digit.

Your task is to count how many good digit strings of length n exist. Since this count can be astronomically large, return the result modulo 10^9 + 7.

Note: A digit string may contain leading zeros. For example, "0020" is a valid digit string of length 4.

Examples

Example 1

Input: n = 1

Output: 5

Explanation: A digit string of length 1 has only one position at index 0, which is an even index. The digit must be even: {0, 2, 4, 6, 8}. This gives us exactly 5 good digit strings: "0", "2", "4", "6", and "8".

Example 2

Input: n = 4

Output: 400

Explanation: A digit string of length 4 has positions at indices 0, 1, 2, 3.

  • Index 0 (even): must be one of {0, 2, 4, 6, 8} → 5 choices
  • Index 1 (odd): must be one of {2, 3, 5, 7} → 4 choices
  • Index 2 (even): must be one of {0, 2, 4, 6, 8} → 5 choices
  • Index 3 (odd): must be one of {2, 3, 5, 7} → 4 choices

Since choices at each position are independent, the total count is 5 × 4 × 5 × 4 = 400.

Example 3

Input: n = 50

Output: 564908303

Explanation: With 50 positions, there are 25 even-indexed positions (each with 5 choices) and 25 odd-indexed positions (each with 4 choices). The raw count is 5^25 × 4^25, an astronomically large number. After taking modulo 10^9 + 7, the result is 564,908,303.

Constraints

  • 1 ≤ n ≤ 10^15

Editorial

Brute Force

Intuition

The most straightforward way to count good digit strings is to actually build every possible valid string and count them one by one. We can use recursion: at each position, we try every valid digit — even digits at even indices and prime digits at odd indices — then recurse to the next position. When we fill all n positions, we have found one valid good number, so we add one to our total.

Think of it like filling out a form with n blank boxes. Each box has specific allowed values depending on its position. You systematically try every allowed value in each box. For each complete form, you increment your tally. Once every combination has been explored, you report the final count.

Step-by-Step Explanation

Let's trace through with n = 4. We build every valid string by choosing digits position by position.

Step 1: Start with an empty string of 4 blank positions: [_, _, _, _]. Begin filling from position 0.

Step 2: Position 0 is an even index. Choose the first even digit: 0. Partial string: [0, _, _, _]. Move to position 1.

Step 3: Position 1 is an odd index. Choose the first prime digit: 2. Partial string: [0, 2, _, _]. Move to position 2.

Step 4: Position 2 is an even index. Choose the first even digit: 0. Partial string: [0, 2, 0, _]. Move to position 3.

Step 5: Position 3 is an odd index. Choose the first prime digit: 2. Complete string: [0, 2, 0, 2] → "0202". This is a valid good number! Count = 1.

Step 6: Backtrack to position 3 and try the next prime digit: 3. String becomes [0, 2, 0, 3] → "0203". Valid! Count = 2.

Step 7: Try digit 5 at position 3. String: [0, 2, 0, 5] → "0205". Valid! Count = 3.

Step 8: Try digit 7 at position 3. String: [0, 2, 0, 7] → "0207". Valid! Count = 4. All 4 prime digits tried at position 3.

Step 9: Backtrack to position 2, try next even digit: 2. String becomes [0, 2, 2, _]. Fill position 3 with all 4 prime choices to get "0222", "0223", "0225", "0227". Count = 8.

Step 10: Continue this exhaustive process. For each of the 5 choices at position 0, there are 4 choices at position 1, 5 at position 2, and 4 at position 3. Every branch produces a valid string.

Step 11: Total valid strings enumerated = 5 × 4 × 5 × 4 = 400.

Recursive Enumeration of Good Digit Strings (n=4) — Watch how we build valid digit strings position by position, backtracking to explore all valid combinations at each position.

Algorithm

  1. Define the set of valid even digits: {0, 2, 4, 6, 8} (5 choices)
  2. Define the set of valid prime digits: {2, 3, 5, 7} (4 choices)
  3. Use recursion starting from position 0:
    • If position equals n, we have built a complete valid string — increment count
    • If current position is an even index, try each of the 5 even digits and recurse to position + 1
    • If current position is an odd index, try each of the 4 prime digits and recurse to position + 1
  4. Return the final count modulo 10^9 + 7

Code

class Solution {
public:
    int countGoodNumbers(long long n) {
        const int MOD = 1e9 + 7;
        long long count = 0;

        function<void(long long)> enumerate = [&](long long pos) {
            if (pos == n) {
                count++;
                return;
            }
            int choices = (pos % 2 == 0) ? 5 : 4;
            for (int c = 0; c < choices; c++) {
                enumerate(pos + 1);
            }
        };

        enumerate(0);
        return count % MOD;
    }
};
class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10**9 + 7
        count = 0

        def enumerate(pos):
            nonlocal count
            if pos == n:
                count += 1
                return
            choices = 5 if pos % 2 == 0 else 4
            for _ in range(choices):
                enumerate(pos + 1)

        enumerate(0)
        return count % MOD
class Solution {
    private long count = 0;
    private static final int MOD = 1_000_000_007;

    public int countGoodNumbers(long n) {
        enumerate(0, n);
        return (int)(count % MOD);
    }

    private void enumerate(long pos, long n) {
        if (pos == n) {
            count++;
            return;
        }
        int choices = (pos % 2 == 0) ? 5 : 4;
        for (int c = 0; c < choices; c++) {
            enumerate(pos + 1, n);
        }
    }
}

Complexity Analysis

Time Complexity: O(5^⌈n/2⌉ × 4^⌊n/2⌋)

The recursion explores every valid digit string. At each even-indexed position, we branch into 5 recursive calls, and at each odd-indexed position we branch into 4 calls. The total number of complete strings (leaf nodes) is 5^⌈n/2⌉ × 4^⌊n/2⌋, which grows exponentially with n. This can also be expressed as approximately O(20^(n/2)).

Space Complexity: O(n)

The recursion stack goes n levels deep — one level per position in the string. No additional data structures are used beyond the call stack.

Why This Approach Is Not Efficient

The recursive enumeration generates every single valid string, and the number of valid strings grows exponentially. For n = 4, that means exploring 400 paths — no problem. But for n = 20, it's 5^10 × 4^10 ≈ 10^13 — far more than any computer can process in a reasonable time. For the given constraint n ≤ 10^15, the number of valid strings would be incomprehensibly large.

The fundamental inefficiency is that we are actually constructing each string to count it. But we don't need to know which strings are valid — we just need to know how many there are. Every time we place digit 0 at position 0, the number of ways to fill positions 1 through n-1 is exactly the same as when we place digit 2, 4, 6, or 8 at position 0. We can exploit this independence to skip the enumeration entirely and just count using multiplication.

Better Approach - Multiplication Principle

Intuition

Here is the crucial realization: the digit placed at position 0 has absolutely no effect on which digits are valid at position 1, or any other position. Each position's constraint depends only on whether its index is even or odd — nothing else.

This means positions are independent. When choices at each stage are independent, we can use the multiplication principle from combinatorics: the total number of outcomes equals the product of choices at each stage.

Instead of generating every string, we simply walk through positions 0 to n-1. At each position, we know exactly how many digits are allowed (5 for even indices, 4 for odd indices). We multiply these counts together to get the total.

Imagine a combination lock with n dials. Each dial can show a different number of values depending on its position. The total number of combinations is just the product of options on each dial — you never need to spin through every combination to know the count.

Step-by-Step Explanation

Let's trace through with n = 4. Instead of building actual strings, we count the number of valid choices at each position and multiply them together.

Step 1: Initialize our running count to 1. We will multiply in the choices for each position.

Step 2: Position 0: index 0 is even (0 % 2 = 0). Even-indexed positions accept an even digit. Available even digits: {0, 2, 4, 6, 8} → 5 choices.

Step 3: Update count: count = 1 × 5 = 5. After processing position 0, there are 5 possible partial strings of length 1.

Step 4: Position 1: index 1 is odd (1 % 2 = 1). Odd-indexed positions accept a prime digit. Available prime digits: {2, 3, 5, 7} → 4 choices.

Step 5: Update count: count = 5 × 4 = 20. After processing positions 0 and 1, there are 20 possible partial strings of length 2.

Step 6: Position 2: index 2 is even (2 % 2 = 0). Choices: {0, 2, 4, 6, 8} → 5 choices.

Step 7: Update count: count = 20 × 5 = 100.

Step 8: Position 3: index 3 is odd (3 % 2 = 1). Choices: {2, 3, 5, 7} → 4 choices.

Step 9: Update count: count = 100 × 4 = 400. All 4 positions processed.

Step 10: Result: There are 400 good digit strings of length 4.

Iterative Counting: Multiplying Choices Position by Position — Watch how we compute the total count by simply multiplying the number of valid digit choices at each position, without generating any strings.

Algorithm

  1. Initialize result = 1
  2. For each position i from 0 to n - 1:
    • If i is even (i % 2 == 0), multiply result by 5 (five even-digit choices)
    • If i is odd (i % 2 == 1), multiply result by 4 (four prime-digit choices)
    • Take result modulo 10^9 + 7 after each multiplication to prevent overflow
  3. Return result

Code

class Solution {
public:
    int countGoodNumbers(long long n) {
        const long long MOD = 1e9 + 7;
        long long result = 1;
        for (long long i = 0; i < n; i++) {
            if (i % 2 == 0) {
                result = (result * 5) % MOD;
            } else {
                result = (result * 4) % MOD;
            }
        }
        return (int)result;
    }
};
class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10**9 + 7
        result = 1
        for i in range(n):
            if i % 2 == 0:
                result = (result * 5) % MOD
            else:
                result = (result * 4) % MOD
        return result
class Solution {
    public int countGoodNumbers(long n) {
        long MOD = 1_000_000_007;
        long result = 1;
        for (long i = 0; i < n; i++) {
            if (i % 2 == 0) {
                result = (result * 5) % MOD;
            } else {
                result = (result * 4) % MOD;
            }
        }
        return (int)result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through all n positions exactly once. At each position, we perform one modular multiplication, which is a constant-time operation. The total work is proportional to n.

Space Complexity: O(1)

We use only a single variable (result) to track the running product. No additional data structures grow with the input size.

Why This Approach Is Not Efficient

While O(n) is a massive improvement over exponential time, the constraint says n can be up to 10^15 (one quadrillion). An O(n) loop performing 10^15 iterations would take roughly 10^15 / 10^9 = 10^6 seconds — that is about 11.5 days on a modern computer. The typical time limit for competitive programming is 1-2 seconds, requiring at most approximately 10^8 operations.

The key observation for further optimization: notice the repeating pattern in our multiplication. We alternate multiplying by 5 and 4. For a string of length n, we multiply by 5 exactly ⌈n/2⌉ times (once per even-indexed position) and by 4 exactly ⌊n/2⌋ times (once per odd-indexed position). Multiplying the same number by itself k times is just exponentiation: 5^k.

So the total is simply 5^⌈n/2⌉ × 4^⌊n/2⌋. And exponentiation can be computed in O(log k) time using a technique called binary exponentiation (also known as fast power or repeated squaring), which reduces our 10^15 multiplications to about 50.

Bar chart comparing time complexity across three approaches: Recursive Enumeration at 10^32 operations, Iterative Counting at 10^15 operations, and Binary Exponentiation at ~50 operations for n=10^15
Bar chart comparing time complexity across three approaches: Recursive Enumeration at 10^32 operations, Iterative Counting at 10^15 operations, and Binary Exponentiation at ~50 operations for n=10^15

Optimal Approach - Fast Modular Exponentiation

Intuition

Building on the multiplication principle, we recognize a clean mathematical pattern:

  • There are ⌈n/2⌉ even-indexed positions, each with 5 choices
  • There are ⌊n/2⌋ odd-indexed positions, each with 4 choices
  • Total = 5^⌈n/2⌉ × 4^⌊n/2⌋ mod (10^9 + 7)

Now we need to compute large powers efficiently. Binary exponentiation (also called exponentiation by squaring) is the key technique. Instead of multiplying the base by itself k times (requiring k-1 multiplications), we observe that:

  • If k is even: base^k = (base^(k/2))² — just one recursive call plus one squaring operation
  • If k is odd: base^k = base × base^(k-1) — reduce to the even case

This halves the exponent at each step, giving us only O(log k) multiplications. For k ≈ 10^15 / 2, that is roughly 50 multiplications instead of 10^15 — a spectacular speedup of over 10^13 times.

To prevent numbers from becoming astronomically large during computation, we apply the modulo operation at every multiplication step, using the mathematical property that (a × b) mod m = ((a mod m) × (b mod m)) mod m.

Step-by-Step Explanation

Let's trace through with n = 50 using the formula: total = 5^⌈n/2⌉ × 4^⌊n/2⌋ mod (10^9 + 7).

Step 1: Compute position counts. Even-indexed positions: ⌈50/2⌉ = 25. Odd-indexed positions: ⌊50/2⌋ = 25. We need 5^25 × 4^25 mod (10^9 + 7). Let's compute pow(5, 25) using binary exponentiation.

Step 2: pow(5, 25): exponent 25 is odd, so pow(5, 25) = 5 × pow(5, 24). Recurse into pow(5, 24).

Step 3: pow(5, 24): exponent 24 is even, so pow(5, 24) = pow(5, 12)². Recurse into pow(5, 12).

Step 4: pow(5, 12): exponent 12 is even, so pow(5, 12) = pow(5, 6)². Recurse into pow(5, 6).

Step 5: pow(5, 6): exponent 6 is even, so pow(5, 6) = pow(5, 3)². Recurse into pow(5, 3).

Step 6: pow(5, 3): exponent 3 is odd, so pow(5, 3) = 5 × pow(5, 2). Recurse into pow(5, 2).

Step 7: pow(5, 2): exponent 2 is even, so pow(5, 2) = pow(5, 1)². Recurse into pow(5, 1).

Step 8: pow(5, 1): exponent 1 is odd, so pow(5, 1) = 5 × pow(5, 0). Recurse into pow(5, 0).

Step 9: pow(5, 0): base case! Any number raised to power 0 is 1. Start unwinding the recursion.

Step 10: Unwind: pow(5, 1) = 5 × pow(5, 0) = 5 × 1 = 5.

Step 11: Unwind: pow(5, 2) = pow(5, 1)² = 5² = 25.

Step 12: Unwind: pow(5, 3) = 5 × pow(5, 2) = 5 × 25 = 125.

Step 13: Unwind: pow(5, 6) = pow(5, 3)² = 125² = 15,625.

Step 14: Unwind: pow(5, 12) = pow(5, 6)² = 15,625² = 244,140,625.

Step 15: Unwind: pow(5, 24) = pow(5, 12)² = 244,140,625² mod (10^9 + 7) = 358,158,117. Here the squared value exceeds 10^9 + 7, so we take the modulo.

Step 16: Unwind: pow(5, 25) = 5 × 358,158,117 mod (10^9 + 7) = 790,790,578.

Step 17: Compute pow(4, 25) mod (10^9 + 7) = 898,961,331 using the same binary exponentiation technique.

Result: Final answer = (790,790,578 × 898,961,331) mod (10^9 + 7) = 564,908,303.

We computed the result using only about 8 recursive calls per power, instead of 25 iterative multiplications or 10^15. That is the power of binary exponentiation!

Binary Exponentiation: Computing pow(5, 25) mod (10⁹+7) — Binary exponentiation halves the exponent at each step, computing large powers in O(log n) recursive calls instead of n multiplications.

Algorithm

  1. Compute even_positions = ⌈n/2⌉ = (n + 1) / 2
  2. Compute odd_positions = ⌊n/2⌋ = n / 2
  3. Use binary exponentiation to compute a = pow(5, even_positions) mod (10^9 + 7)
  4. Use binary exponentiation to compute b = pow(4, odd_positions) mod (10^9 + 7)
  5. Return (a × b) mod (10^9 + 7)

Binary exponentiation — pow(base, exp, mod):

  • Initialize result = 1, base = base mod mod
  • While exp > 0:
    • If exp is odd, multiply: result = (result × base) mod mod
    • Halve exponent: exp = exp / 2
    • Square base: base = (base × base) mod mod
  • Return result

Code

class Solution {
public:
    int countGoodNumbers(long long n) {
        long long MOD = 1e9 + 7;
        long long evenPos = (n + 1) / 2;
        long long oddPos = n / 2;
        long long result = (power(5, evenPos, MOD) * power(4, oddPos, MOD)) % MOD;
        return (int)result;
    }

    long long power(long long base, long long exp, long long mod) {
        long long result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
            }
            exp /= 2;
            base = (base * base) % mod;
        }
        return result;
    }
};
class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10**9 + 7
        even_positions = (n + 1) // 2
        odd_positions = n // 2
        return (pow(5, even_positions, MOD) * pow(4, odd_positions, MOD)) % MOD
class Solution {
    private static final long MOD = 1_000_000_007;

    public int countGoodNumbers(long n) {
        long evenPos = (n + 1) / 2;
        long oddPos = n / 2;
        long result = (power(5, evenPos) * power(4, oddPos)) % MOD;
        return (int)result;
    }

    private long power(long base, long exp) {
        long result = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % MOD;
            }
            exp /= 2;
            base = (base * base) % MOD;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(log n)

Binary exponentiation halves the exponent at each step. For an exponent of value k, this requires O(log k) multiplications. Since both exponents are approximately n/2, the total time is O(log(n/2)) = O(log n). Each multiplication involves numbers at most (10^9 + 7)², which fits in a 64-bit integer, so each operation is O(1). For n = 10^15, we perform roughly 2 × log₂(5 × 10^14) ≈ 100 multiplications — essentially instantaneous.

Space Complexity: O(1) for the iterative implementation, O(log n) for the recursive implementation

The iterative version of binary exponentiation uses only a constant number of variables: result, base, and exp. The recursive version uses O(log n) stack frames. Both are extremely efficient. In practice, the iterative implementation is preferred to avoid stack overflow for very large exponents.