Count Good Numbers solution and explanation
Google
Infosys
9 more videos on this problem
Leetcode Solution : Count Good NumbersFraz · 17:22 · 70K views
Count Good Numbers | Simple Explanation | Leetcode 1922 | codestorywithMIKcodestorywithMIK · 14:13 · 30K views
Count Good Numbers - Leetcode 1922 - PythonNeetCodeIO · 21:51 · 15K views
Count Good Numbers | Leetcode 1922Techdose · 8:06 · 9K views
Count Good Numbers | LeetCode 1922 | Coders CampCoders Camp · 11:09 · 6K views
1922. Count Good Numbers (Leetcode Medium)Programming Live with Larry · 11:14 · 2K views
LeetCode 1922 Count Good Numbers | Binary Exponentiation | Detailed Explanation | Google MetaCode Harmony · 19:21 · 2K views
Leetcode 1922: Count Good Numbers | Java SolutioncodingX krishna · 13:55 · 355 views
Daily Leetcode #1839: Apr 13, 2025 - 1922. Count Good NumbersProgramming Live with Larry · 5:23 · 344 views
1922. Count Good Numbers | Leetcode Daily - PythonLeetcode Daily · 8:50 · 291 views
The problem
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 (2and8) at even positions are even and the digits (5and2) at odd positions are prime. However,"3245"is not good because3is 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 109 + 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 <= 1015
Approach overview
Problem Overview: You need to count how many digit strings of length n are considered good. A digit at an even index (0‑based) must be an even digit (0,2,4,6,8) and a digit at an odd index must be a prime digit (2,3,5,7). Because n can be extremely large, directly constructing or iterating through strings is impossible. The task reduces to counting valid choices using math and computing the result modulo 1e9 + 7.
Approach 1: Iterative Approach with Modulo Calculations (O(n) time, O(1) space)
This approach computes the number of choices position by position. Every even index contributes 5 choices (even digits), and every odd index contributes 4 choices (prime digits). Iterate from 0 to n-1, multiply the running result by 5 or 4 depending on the index parity, and apply modulo 1e9+7 at each step to avoid overflow. The logic is straightforward and mirrors the problem definition directly. However, when n is very large (up to 10^15 in constraints), an O(n) loop becomes impractical.
Approach 2: Combine Properties of Even and Prime Numbers (Fast Power) (O(log n) time, O(log n) space)
The key observation: positions are independent. Count how many even indices and odd indices exist instead of processing each one. Even indices = ceil(n / 2), odd indices = floor(n / 2). Each even index has 5 choices and each odd index has 4 choices. The total number of good numbers becomes 5^(ceil(n/2)) * 4^(floor(n/2)). Compute these powers using fast modular exponentiation (binary exponentiation), which repeatedly squares the base and halves the exponent. This reduces the runtime from O(n) to O(log n). Implementations often use recursion or iterative binary exponentiation, making this approach a strong example of combining math with recursion and modular arithmetic.
Recommended for interviews: Interviewers expect the mathematical reduction and fast exponentiation approach. Starting with the iterative counting idea demonstrates you understand the constraints and combinatorics. The optimized solution shows you recognize exponential growth patterns and apply modular exponentiation to handle huge inputs efficiently.
Approach 1: Combine Properties of Even and Prime Numbers
The task is to construct a good digit string of length n. We need to ensure that digits at even indices are even and those at odd indices are prime numbers.
- The even-indexed positions (0, 2, 4, ...) should contain one of the five even digits (0, 2, 4, 6, 8).
- The odd-indexed positions (1, 3, 5, ...) should contain one of the four prime numbers (2, 3, 5, 7).
We calculate the number of ways to fill the even and odd positions independently.
MOD = 10**9 + 7
def power(base, exp, mod):
result = 1
base %= mod
while exp > 0:
if exp % 2 == 1:
result = (result * base) % mod
exp >>= 1
base = (base * base) % mod
return result
def countGoodNumbers(n):
even_digits = (n + 1) // 2
prime_digits = n // 2
return (power(5, even_digits, MOD) * power(4, prime_digits, MOD)) % MOD
print(countGoodNumbers(50))public class Solution {
private static final int MOD = 1000000007;
private long power(long base, long exp, long mod) {
long result = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) result = (result * base) % mod;
exp >>= 1;
base = (base * base) % mod;
}
return result;
}
public int countGoodNumbers(long n) {
long even_digits = (n + 1) / 2;
long prime_digits = n / 2;
return (int)((power(5, even_digits, MOD) * power(4, prime_digits, MOD)) % MOD);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.countGoodNumbers(50));
}
}#include <iostream>
using namespace std;
#define MOD 1000000007
long long power(long long base, long long exp, long long mod) {
long long result = 1;
base = base % mod;
while (exp > 0) {
if (exp % 2 == 1)
result = (result * base) % mod;
exp = exp >> 1;
base = (base * base) % mod;
}
return result;
}
int countGoodNumbers(long long n) {
long long even_digits = (n + 1) / 2;
long long prime_digits = n / 2;
return (power(5, even_digits, MOD) * power(4, prime_digits, MOD)) % MOD;
}
int main() {
cout << countGoodNumbers(50) << endl;
return 0;
}const MOD = 1000000007;
function power(base, exp, mod) {
let result = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 === 1) {
result = (result * base) % mod;
}
exp >>= 1;
base = (base * base) % mod;
}
return result;
}
function countGoodNumbers(n) {
const evenDigits = Math.floor((n + 1) / 2);
const primeDigits = Math.floor(n / 2);
return (power(5, evenDigits, MOD) * power(4, primeDigits, MOD)) % MOD;
}
console.log(countGoodNumbers(50));#include <stdio.h>
#define MOD 1000000007
long long power(long long base, long long exp, long long mod) {
long long result = 1;
base = base % mod;
while (exp > 0) {
if (exp % 2 == 1)
result = (result * base) % mod;
exp = exp >> 1;
base = (base * base) % mod;
}
return result;
}
int countGoodNumbers(long long n) {
long long even_digits = (n + 1) / 2;
long long prime_digits = n / 2;
return (power(5, even_digits, MOD) * power(4, prime_digits, MOD)) % MOD;
}
int main() {
printf("%d\n", countGoodNumbers(50));
return 0;
}using System;
class Program
{
const int MOD = 1000000007;
static long Power(long baseNum, long exp, long mod)
{
long result = 1;
baseNum %= mod;
while (exp > 0)
{
if ((exp & 1) == 1)
result = (result * baseNum) % mod;
exp >>= 1;
baseNum = (baseNum * baseNum) % mod;
}
return result;
}
static int CountGoodNumbers(long n)
{
long evenDigits = (n + 1) / 2;
long primeDigits = n / 2;
return (int)((Power(5, evenDigits, MOD) * Power(4, primeDigits, MOD)) % MOD);
}
static void Main()
{
Console.WriteLine(CountGoodNumbers(50));
}
}This Python solution makes use of the built-in integer capabilities to ensure arithmetic remains efficient, employing modular exponentiation to handle large bases and exponents.
The time complexity is O(log n), and the space complexity is O(1).
Approach 2: Iterative Approach with Modulo Calculations
An iterative approach can also be used to solve this problem by calculating the number of valid numbers at each step sequentially rather than relying on exponentiation.
MOD = 10**9 + 7
def countGoodNumbers(n):
result = 1
for i in range(n):
result = (result * (5 if i % 2 == 0 else 4)) % MOD
return result
print(countGoodNumbers(50))public class Solution {
private static final int MOD = 1000000007;
public int countGoodNumbers(long n) {
long result = 1;
for (long i = 0; i < n; i++) {
result = (result * ((i % 2 == 0) ? 5 : 4)) % MOD;
}
return (int) result;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.countGoodNumbers(50));
}
}#include <iostream>
using namespace std;
#define MOD 1000000007
long long countGoodNumbers(long long n) {
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 result;
}
int main() {
cout << countGoodNumbers(50) << endl;
return 0;
}const MOD = 1000000007;
function countGoodNumbers(n) {
let result = 1;
for (let i = 0; i < n; i++) {
result = (result * ((i % 2 === 0) ? 5 : 4)) % MOD;
}
return result;
}
console.log(countGoodNumbers(50));#include <stdio.h>
#define MOD 1000000007
long long countGoodNumbers(long long n) {
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 result;
}
int main() {
printf("%lld\n", countGoodNumbers(50));
return 0;
}using System;
class Program
{
const int MOD = 1000000007;
static int CountGoodNumbers(long n)
{
long result = 1;
for (long i = 0; i < n; i++)
{
result = (result * ((i % 2 == 0) ? 5 : 4)) % MOD;
}
return (int)result;
}
static void Main()
{
Console.WriteLine(CountGoodNumbers(50));
}
}In Python, the solution involves using a loop to multiply by either 5 or 4 depending on the index, followed by taking a modulus to fit within the required limits.
Time complexity is O(n) and space complexity is O(1) as result values are directly updated.
Approach 3: Fast Exponentiation
For a "good number" of length n, the even-indexed positions have \lceil \frac{n}{2} \rceil = \lfloor \frac{n + 1}{2} \rfloor digits, and these positions can be filled with 5 different digits (0, 2, 4, 6, 8). The odd-indexed positions have \lfloor \frac{n}{2} \rfloor digits, and these positions can be filled with 4 different digits (2, 3, 5, 7). Therefore, the total number of "good numbers" of length n is:
$
ans = 5^{\lceil \frac{n}{2} \rceil} times 4^{\lfloor \frac{n}{2} \rfloor}
We can use fast exponentiation to compute 5^{\lceil \frac{n}{2} \rceil} and 4^{\lfloor \frac{n}{2} \rfloor}. The time complexity is O(log n), and the space complexity is O(1)$.
function countGoodNumbers(n: number): number {
const mod = 1000000007n;
const qpow = (x: bigint, n: bigint): bigint => {
let res = 1n;
while (n > 0n) {
if (n & 1n) {
res = (res * x) % mod;
}
x = (x * x) % mod;
n >>= 1n;
}
return res;
};
const a = qpow(5n, BigInt(n + 1) / 2n);
const b = qpow(4n, BigInt(n) / 2n);
return Number((a * b) % mod);
}const mod int64 = 1e9 + 7
func countGoodNumbers(n int64) int {
return int(myPow(5, (n+1)>>1) * myPow(4, n>>1) % mod)
}
func myPow(x, n int64) int64 {
var res int64 = 1
for n != 0 {
if (n & 1) == 1 {
res = res * x % mod
}
x = x * x % mod
n >>= 1
}
return res
}Complexity comparison
| Approach | Complexity |
|---|---|
| Combine Properties of Even and Prime Numbers | The time complexity is |
| Iterative Approach with Modulo Calculations | Time complexity is |
| Fast Exponentiation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Multiplication with Modulo | O(n) | O(1) | When n is small and you want the most direct implementation matching the problem definition. |
| Mathematical Counting + Fast Modular Exponentiation | O(log n) | O(log n) | Preferred for large n. Uses exponentiation by squaring to compute 5^(ceil(n/2)) and 4^(floor(n/2)) efficiently. |
Frequently asked questions
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.