Count Good Numbers - Practice Coding Problems

Count Good Numbers - Problem

Math Recursion Medium

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^9 + 7.

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

Input & Output

Example 1 — Small Case

$ Input: n = 1

› Output: 5

💡 Note: Single digit at even position 0. Valid digits: 0,2,4,6,8. Total = 5.

Example 2 — Two Positions

$ Input: n = 2

› Output: 20

💡 Note: Position 0 (even): 5 choices, Position 1 (odd): 4 choices. Total = 5 × 4 = 20.

Example 3 — Larger Input

$ Input: n = 50

› Output: 564908303

💡 Note: Even positions: 25, Odd positions: 25. Result = 5²⁵ × 4²⁵ mod (10⁹ + 7).

Constraints

1 ≤ n ≤ 10¹⁵

Visualization

Tap to expand

Understanding the Visualization

Input

String length n=4

Position Rules

Even positions need even digits, odd positions need prime digits

Output

Total count of valid strings

Key Takeaway

🎯 Key Insight: Each position's digit choices are independent - multiply the possibilities!

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is recognizing that positions have independent digit choices. Even positions must use digits {0,2,4,6,8} and odd positions must use {2,3,5,7}. Best approach is mathematical formula: 5^even_positions × 4^odd_positions using fast exponentiation. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula	O(log n)	O(1)	Calculate using combinatorial mathematics
Brute Force Recursion	O(10^n)	O(n)	Try all possible digit combinations recursively

Mathematical Formula — Algorithm Steps

Count even positions: ceil(n/2)
Count odd positions: floor(n/2)
Calculate 5^even_count × 4^odd_count
Use modular exponentiation for large powers

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Positions

Even: ceil(n/2), Odd: floor(n/2)

Choices Per Type

Even: 5 choices, Odd: 4 choices

Multiply Powers

Result = 5^even × 4^odd

Code -

solution.c — C

#include <stdio.h>

const int MOD = 1000000007;

long long powerMod(long long base, int exp, int mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % mod;
        }
        exp >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

int solution(int n) {
    int evenPositions = (n + 1) / 2;  // Positions 0, 2, 4, ...
    int oddPositions = n / 2;         // Positions 1, 3, 5, ...
    
    // Even positions have 5 choices: 0, 2, 4, 6, 8
    // Odd positions have 4 choices: 2, 3, 5, 7
    long long evenChoices = powerMod(5, evenPositions, MOD);
    long long oddChoices = powerMod(4, oddPositions, MOD);
    
    return (evenChoices * oddChoices) % MOD;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int result = solution(n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Fast exponentiation takes O(log n) time for computing powers

⚡ Linearithmic

Space Complexity

O(1)

Only uses constant extra variables

✓ Linear Space

32.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Formula — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler