LeetCode Problem 1922

Difficulty: 🟡 Medium
Topics: Math, Recursion

Solution

LeetCode 1922, Count Good Numbers

Problem Understanding

The problem asks us to count how many digit strings of length n satisfy a specific positional rule.

A digit string is considered "good" when:

• Every digit placed at an even index, meaning indices 0, 2, 4, ..., must itself be an even digit.
• Every digit placed at an odd index, meaning indices 1, 3, 5, ..., must be a prime digit.

The valid even digits are:

0, 2, 4, 6, 8

So there are 5 choices for every even index.

The valid prime digits are:

2, 3, 5, 7

So there are 4 choices for every odd index.

The input n represents the length of the digit string. We must return the total number of valid strings modulo:

10^9 + 7

The constraint is extremely important:

1 <= n <= 10^15

This immediately tells us that generating strings explicitly is impossible. Even iterating n times is acceptable, but anything exponential is completely infeasible. Since n can be as large as one quadrillion, we need a logarithmic time mathematical solution.

There are also several important edge cases:

• n = 1, only index 0 exists, so only even digits matter.
• Very large values of n, where direct multiplication would overflow normal integer ranges in many languages.
• Odd and even lengths behave slightly differently because the number of even-index positions and odd-index positions are not equal when n is odd.

For a length n:

• Number of even indices = (n + 1) // 2
• Number of odd indices = n // 2

The final count becomes:

5^(even_positions) * 4^(odd_positions)

computed modulo 10^9 + 7.

Approaches

Brute Force Approach

The brute force approach would generate every possible digit string of length n and check whether it satisfies the conditions.

For each position:

• If the position is even, verify the digit is one of {0,2,4,6,8}.
• If the position is odd, verify the digit is one of {2,3,5,7}.

Since each position can contain 10 digits, the total number of strings is:

$10^n$

This becomes astronomically large even for modest values of n.

For example:

• n = 20 already gives 10^20 possibilities.
• The constraint allows n = 10^15, making brute force completely impossible.

The brute force method is correct because it examines every possible string, but it is far too slow.

Optimal Approach

The key observation is that each position is independent.

At every even index:

• There are exactly 5 valid choices.

At every odd index:

• There are exactly 4 valid choices.

If we know how many even and odd positions exist, we can directly compute the answer using multiplication.

Let:

even_positions = (n + 1) // 2
odd_positions = n // 2

Then the total number of good strings is:

$5^{\lfloor\frac{n+1}{2}\rfloor} \times 4^{\lfloor\frac{n}{2}\rfloor}$

However, these exponents are extremely large, so we must compute powers efficiently using fast exponentiation, also called binary exponentiation.

Binary exponentiation computes:

$a^b \bmod m$

in O(log b) time instead of O(b) time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(10^n)	O(n)	Generates every possible digit string
Optimal	O(log n)	O(1)	Uses combinatorics and fast modular exponentiation

Algorithm Walkthrough

1. Define the modulo constant.

The problem requires all results modulo 10^9 + 7, so we store:

MOD = 1_000_000_007

2. Count how many even-index positions exist.

Indices start at 0, so for odd lengths there is one extra even index.

We compute:

even_positions = (n + 1) // 2

3. Count how many odd-index positions exist.

Every remaining position is odd-indexed:

odd_positions = n // 2

4. Compute the contribution from even positions.

Each even position has 5 choices:

5^(even_positions)

Because the exponent may be huge, we compute it modulo MOD using fast exponentiation. 5. Compute the contribution from odd positions.

Each odd position has 4 choices:

4^(odd_positions)

Again, we use modular exponentiation. 6. Multiply the two results together.

Since choices are independent, we multiply them:

answer = (even_part * odd_part) % MOD

7. Return the final result.

Why it works

The algorithm works because each index contributes independently to the total number of valid strings.

Every even index always has exactly 5 valid choices, regardless of what appears elsewhere. Every odd index always has exactly 4 valid choices. By the multiplication principle from combinatorics, the total number of valid strings equals the product of the choices for each position.

Fast exponentiation guarantees that very large powers are computed efficiently while preserving correctness under modular arithmetic.

Python Solution

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 1_000_000_007

        even_positions = (n + 1) // 2
        odd_positions = n // 2

        even_count = pow(5, even_positions, MOD)
        odd_count = pow(4, odd_positions, MOD)

        return (even_count * odd_count) % MOD

The implementation directly follows the mathematical observation developed earlier.

First, the code computes how many even-index and odd-index positions exist. Because indexing starts at zero, the number of even positions is slightly larger when n is odd.

Python's built-in pow(base, exponent, mod) performs fast modular exponentiation internally. This is extremely efficient and runs in logarithmic time.

The result for even positions and odd positions is computed separately, then multiplied together modulo MOD.

This solution is concise because Python already provides optimized modular exponentiation.

Go Solution

func countGoodNumbers(n int64) int {
	const MOD int64 = 1_000_000_007

	evenPositions := (n + 1) / 2
	oddPositions := n / 2

	evenCount := modPow(5, evenPositions, MOD)
	oddCount := modPow(4, oddPositions, MOD)

	return int((evenCount * oddCount) % MOD)
}

func modPow(base, exponent, mod int64) int64 {
	result := int64(1)

	base %= mod

	for exponent > 0 {
		if exponent%2 == 1 {
			result = (result * base) % mod
		}

		base = (base * base) % mod
		exponent /= 2
	}

	return result
}

The Go version implements binary exponentiation manually because Go does not provide a built-in modular power function like Python.

All calculations use int64 to avoid overflow issues during multiplication. The modulo operation is applied after every multiplication so values remain bounded.

The algorithmic logic is otherwise identical to the Python implementation.

Worked Examples

Example 1

Input: n = 1

Step 1: Count positions

Type	Count
Even positions	(1 + 1) // 2 = 1
Odd positions	1 // 2 = 0

Step 2: Compute possibilities

Component	Value
Even contribution	5^1 = 5
Odd contribution	4^0 = 1

Step 3: Final answer

Calculation	Result
5 × 1	5

Output:

5

Example 2

Input: n = 4

Step 1: Count positions

Type	Count
Even positions	(4 + 1) // 2 = 2
Odd positions	4 // 2 = 2

Step 2: Compute possibilities

Component	Value
Even contribution	5^2 = 25
Odd contribution	4^2 = 16

Step 3: Final answer

Calculation	Result
25 × 16	400

Output:

400

Example 3

Input: n = 50

Step 1: Count positions

Type	Count
Even positions	25
Odd positions	25

Step 2: Compute powers modulo MOD

Component	Expression
Even contribution	5^25 mod MOD
Odd contribution	4^25 mod MOD

Using fast modular exponentiation:

Result
564908303

Output:

564908303

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Binary exponentiation processes exponent bits
Space	O(1)	Only a few variables are used

The dominant operation is modular exponentiation. Binary exponentiation repeatedly squares the base and halves the exponent, so the number of iterations grows logarithmically with n.

No additional data structures proportional to input size are allocated, so the space complexity remains constant.

Test Cases

sol = Solution()

assert sol.countGoodNumbers(1) == 5          # Single even-index position
assert sol.countGoodNumbers(2) == 20         # One even and one odd position
assert sol.countGoodNumbers(3) == 100        # Two even positions, one odd
assert sol.countGoodNumbers(4) == 400        # Example from prompt
assert sol.countGoodNumbers(5) == 2000       # Odd length case
assert sol.countGoodNumbers(50) == 564908303 # Large example from prompt

# Small boundary values
assert sol.countGoodNumbers(6) == 8000       # Balanced even/odd positions
assert sol.countGoodNumbers(7) == 40000      # Extra even position

# Very large input stress test
result = sol.countGoodNumbers(10**15)
assert isinstance(result, int)               # Ensures large input works

# Modulo behavior test
assert 0 <= sol.countGoodNumbers(10**15) < 1_000_000_007

Test Summary

Test	Why
n = 1	Smallest valid input
n = 2	Simplest case with both position types
n = 3	Odd length handling
n = 4	Provided example
n = 5	Additional odd-length verification
n = 50	Large provided example
n = 6	Balanced even and odd counts
n = 7	Unequal position counts
n = 10^15	Stress test for logarithmic performance
Modulo range check	Ensures proper modular arithmetic

Edge Cases

Edge Case 1, Minimum Length

When n = 1, there is only index 0, which is an even index. No odd positions exist.

A common mistake is incorrectly assuming half the positions are odd and half are even. The implementation correctly computes:

even_positions = (1 + 1) // 2 = 1
odd_positions = 1 // 2 = 0

This produces the correct answer of 5.

Edge Case 2, Odd Length Strings

For odd values of n, there is always one more even-index position than odd-index position because indexing starts at zero.

For example:

n = 5
indices = 0 1 2 3 4

Even indices are:

0, 2, 4

Odd indices are:

1, 3

A buggy implementation might use n // 2 for both counts, which would miss one position. The implementation avoids this by using (n + 1) // 2 for even positions.

Edge Case 3, Extremely Large Inputs

The constraint allows:

n <= 10^15

Direct multiplication loops or recursive expansion would be far too slow.

The implementation handles this correctly using binary exponentiation, which reduces the complexity to O(log n). Even for the maximum possible input, the computation completes quickly.

Edge Case 4, Integer Overflow

Intermediate values like:

5^(10^15)

are unimaginably large.

Without modular arithmetic applied during exponentiation, integer overflow would occur in fixed-width integer languages like Go or Java.

The implementation applies modulo operations during every multiplication step, ensuring all values remain within safe bounds throughout computation.