Is Count Good Numbers easy or hard?

Count Good Numbers is rated Medium on LeetCode. The counting logic is simple, but recognizing the need for fast modular exponentiation for very large n makes it slightly more challenging.

How to solve Count Good Numbers in O(log n)?

First count how many even and odd indices exist: ceil(n/2) and floor(n/2). Compute 5^(evenCount) and 4^(oddCount) using fast modular exponentiation. Multiply the two results and apply modulo 1e9+7. Binary exponentiation reduces repeated multiplication to logarithmic time.

What is the best approach for Count Good Numbers?

The optimal approach uses mathematical counting with fast modular exponentiation. Even indices have 5 choices and odd indices have 4 choices, so the total becomes 5^(ceil(n/2)) * 4^(floor(n/2)). Binary exponentiation computes these powers in O(log n) time while applying modulo 1e9+7.

Is Count Good Numbers asked at Google/Amazon/Meta?

This style of problem frequently appears in interviews at companies like Amazon and Google because it tests mathematical reasoning and modular exponentiation. Candidates must recognize combinatorial counting and apply fast power techniques for very large inputs.

What data structure is used in Count Good Numbers?

The problem does not require complex data structures. It relies on mathematical counting and modular arithmetic. The main technique is fast exponentiation implemented through recursion or iterative binary exponentiation.

What is the time complexity of Count Good Numbers?

The optimal solution runs in O(log n) time using fast exponentiation. Instead of iterating through all n positions, it computes powers of 5 and 4 using exponentiation by squaring. Space complexity is O(log n) if implemented recursively or O(1) iteratively.

Count Good Numbers Python or Java solution approach?

Both Python and Java implementations typically compute evenCount = (n+1)//2 and oddCount = n//2. Then use a fast power function to compute pow(5, evenCount, MOD) and pow(4, oddCount, MOD). Multiply the results modulo 1e9+7 to get the final answer.

Description Hints 2 Solution Video 17:22

1922. Count Good Numbers

Medium58.1% acceptance7 companies

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).

For example, "2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, "3245" is not good because 3 is at an even index but is not even.

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 that may contain leading zeros.

Example 1:

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

Example 2:

Input: n = 4
Output: 400

Example 3:

Input: n = 50
Output: 564908303

Constraints:

1 <= n <= 10¹⁵

Asked at 7 companies

Google Amazon Microsoft Bloomberg

Infosys Visa Meta

Topics

Math Recursion

Hints open one at a time

Hint 1

Is there a formula we can use to find the count of all the good numbers?

Hint 2

Exponentiation can be done very fast if we looked at the binary bits of n.

17:22

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution