LeetCode 1922 - Count Good Numbers

Problem Statement

A digit string is good if:

• The digits at even indices (0-based) are even: {0, 2, 4, 6, 8}
• The digits at odd indices are prime: {2, 3, 5, 7}

Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 10⁹ + 7.

A digit string is a string consisting of digits 0 through 9 and may contain leading zeros.

---

Example

Input:
n = 1
Output:
5
Explanation: The good numbers of length 1 are "0", "2", "4", "6", "8".

Input:
n = 4
Output:
400

---

Intuition

• Even positions have 5 options → {0, 2, 4, 6, 8}
• Odd positions have 4 options → {2, 3, 5, 7}
• Use modular exponentiation to compute large powers.

---

Approach

1. Count how many positions are even and how many are odd:
   • Even positions = (n + 1) // 2
   • Odd positions = n // 2
2. Use modular exponentiation to compute:
   • (5^{even} \mod (10^9 + 7))
   • (4^{odd} \mod (10^9 + 7))
3. Multiply the two results and take modulo again.

---

Complexity

• Time Complexity:
  (O(\log n)) — fast exponentiation
• Space Complexity:
  (O(1))

---

Python Code

class Solution(object):
    def countGoodNumbers(self, n):
        MOD = 10**9 + 7

        def power(x, y):
            result = 1
            x %= MOD
            while y > 0:
                if y % 2 == 1:
                    result = (result * x) % MOD
                x = (x * x) % MOD
                y //= 2
            return result

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

        return (power(5, even_positions) * power(4, odd_positions)) % MOD

🚀 Created by Coding Moves

Subscribe to Coding Moves for more coding tutorials, projects, and problem-solving strategies!