We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Good Numbers

Number: 2050

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, Bloomberg, Amazon, Meta, Uber

Problem Description

Given an integer n, we need to determine the total number of good digit strings of length n such that digits at even indices are even (0, 2, 4, 6, 8) and digits at odd indices are prime (2, 3, 5, or 7). A digit string is a string consisting of digits 0 through 9 (with possible leading zeros). The answer should be returned modulo 10^9 + 7.

Key Insights

  • The string has n positions, where positions are 0-indexed.
  • Even indices must contain one of 5 even digits {0, 2, 4, 6, 8}.
  • Odd indices must contain one of 4 prime digits {2, 3, 5, 7}.
  • Count the number of even index positions as ceil(n / 2) and odd index positions as floor(n / 2).
  • The total good numbers equals 5^(ceil(n / 2)) * 4^(floor(n / 2)) modulo 10^9 + 7.
  • Use fast modular exponentiation due to the large constraint on n (up to 10^15).

Space and Time Complexity

Time Complexity: O(log n) due to fast modular exponentiation. Space Complexity: O(1) as only a fixed amount of memory is used.

Solution

We determine the count of good digit strings by dividing the positions into even and odd index positions. Even indexes must be one of the 5 even digits, so they contribute 5 possibilities each; odd indexes must be one of the 4 prime digits, and they contribute 4 possibilities each. If n is the length, then:

  • Number of even indexed positions = ceil(n / 2)
  • Number of odd indexed positions = floor(n / 2)

Thus, the total number of good strings is: 5^(ceil(n / 2)) * 4^(floor(n / 2)) modulo (10^9 + 7).

To compute these large exponents efficiently, we use fast modular exponentiation (also known as modular power). This ensures that even for n as large as 10^15, the exponents are calculated quickly.

The provided code solutions in Python, JavaScript, C++, and Java include detailed inline comments to clarify each step.

Code Solutions

# Function to perform fast modular exponentiation
def mod_pow(base, exp, mod):
    result = 1
    while exp > 0:
        # If the current exponent is odd, multiply the result by base mod mod
        if exp % 2:
            result = (result * base) % mod
        # Square the base and reduce the exponent by half
        base = (base * base) % mod
        exp //= 2
    return result

def countGoodNumbers(n):
    mod = 10**9 + 7
    # Calculate the count of indices for even and odd positions
    even_count = (n + 1) // 2  # ceil(n/2)
    odd_count = n // 2         # floor(n/2)
    # Compute the result using modular exponentiation for both parts
    result = (mod_pow(5, even_count, mod) * mod_pow(4, odd_count, mod)) % mod
    return result

# For example: n = 4 should output 400
print(countGoodNumbers(4))
← Back to All Questions