☕ DSA Java Articles

Topics › Recursion and Backtracking › Get a Strong Hold

Count Good Numbers

Medium TUF ID 222 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A digit string is good if, reading its positions from 0, every digit at an even index is even (0, 2, 4, 6, 8) and every digit at an odd index is a prime (2, 3, 5, 7). Leading zeros are allowed, so "0", "02" and "2582" are all good; "3245" is not (3 at index 0 is odd).

Given n, return the number of good digit strings of length n, modulo 10^9 + 7.

Constraints: 1 ≤ n ≤ 10^15. The size of n is the whole problem: it does not fit in an int, and any algorithm that does one step per position is far too slow.

Example 1

n = 1
answer = 5               // "0", "2", "4", "6", "8"

Example 2

n = 4
answer = 400             // 5 * 4 * 5 * 4

Example 3

n = 50
answer = 564908303       // 5^25 * 4^25 mod (10^9 + 7)

Approach 1: Brute force

Intuition. Enumerate every one of the 10^n digit strings and test each against the rule. This is hopeless beyond n = 7 or so, but it is the quickest way to confirm the counting argument used by the real solutions.

Algorithm.

  1. For every integer v from 0 to 10^n - 1, treat v as a zero-padded string of n digits.
  2. Peel digits off the right; the last digit sits at index n - 1, the one before it at n - 2, and so on.
  3. Reject as soon as an even index holds an odd digit or an odd index holds a non-prime.
  4. Count the survivors.
static long bruteForce(long n) {
    if (n > 7) throw new IllegalArgumentException("brute force is only for n <= 7");
    int len = (int) n;
    long total = 1;
    for (int i = 0; i < len; i++) total *= 10;    // 10^len strings
    long count = 0;
    for (long v = 0; v < total; v++) {
        if (isGood(v, len)) count++;
    }
    return count % MOD;
}

static boolean isGood(long v, int len) {
    for (int index = len - 1; index >= 0; index--) {   // the last digit of v sits at the last index
        int d = (int) (v % 10);
        v /= 10;
        if (index % 2 == 0) {
            if (d % 2 != 0) return false;
        } else if (d != 2 && d != 3 && d != 5 && d != 7) {
            return false;
        }
    }
    return true;
}

Complexity. Time O(10^n · n). Space O(1). The Java file guards the method so it is never called for n > 7.

Approach 2: Better, multiply position by position

Intuition. The choices at different positions are independent: whatever digit sits at index 0, index 1 still has exactly four legal digits. By the multiplication principle the count is the product of the number of choices at each index: 5 for every even index and 4 for every odd one. A loop multiplies them together, reducing modulo 10^9 + 7 after each step so the product stays inside a long.

Algorithm.

  1. result = 1.
  2. For index = 0 .. n - 1: multiply result by 5 if index is even, else by 4, then take the remainder.
  3. Return result.
static long better(long n) {
    long result = 1;
    for (long index = 0; index < n; index++) {
        result = result * (index % 2 == 0 ? 5 : 4) % MOD;
    }
    return result;
}

Complexity. Time O(n). Space O(1).

This is correct for every n, and for n up to a few million it is instant, but the constraint allows n = 10^15. At a billion multiplications per second that loop would run for about eleven days. The product has a closed form, and we need a way to evaluate a huge power quickly.

Approach 3: Optimal, closed form with fast exponentiation

Intuition. Among the indices 0 .. n - 1 there are ceil(n / 2) even ones and floor(n / 2) odd ones, so the answer is

5^ceil(n/2) * 4^floor(n/2)   mod (10^9 + 7)

Computing 5^k for k ≈ 5 × 10^14 is where recursion comes in. b^k = (b^(k/2))^2, with one extra factor b when k is odd. Each level halves the exponent, so about 50 levels suffice for k = 10^15. Taking the remainder after each multiplication keeps every intermediate value below 10^9 + 7, and the product of two such values is below 10^18, safely inside a long.

Algorithm.

  1. evenIndices = (n + 1) / 2, oddIndices = n / 2 (integer division).
  2. modPow(b, k): if k == 0 return 1. Otherwise half = modPow(b, k / 2), result = half² mod M, and if k is odd result = result · b mod M.
  3. Return modPow(5, evenIndices) · modPow(4, oddIndices) mod M.
static long optimal(long n) {
    long evenIndices = (n + 1) / 2;               // indices 0, 2, 4, ...: 5 even digits each
    long oddIndices = n / 2;                      // indices 1, 3, 5, ...: 4 prime digits each
    return modPow(5, evenIndices) * modPow(4, oddIndices) % MOD;
}

static long modPow(long base, long exp) {
    if (exp == 0) return 1;                        // base case: anything to the power 0 is 1
    long half = modPow(base, exp / 2);
    long result = half * half % MOD;
    if (exp % 2 == 1) result = result * base % MOD;
    return result;
}

Dry run for n = 5: evenIndices = 3, oddIndices = 2. modPow(5, 3): modPow(5, 0) = 1, modPow(5, 1) = 1 · 1 · 5 = 5, modPow(5, 3) = 5 · 5 · 5 = 125. modPow(4, 2): modPow(4, 1) = 4, modPow(4, 2) = 16. Answer 125 · 16 = 2000, which matches the brute force.

Complexity. Time O(log n): two exponentiations of about log2(n) levels each. Space O(log n) for the recursion stack, roughly 50 frames at the limit.

A small refinement removes one of the two exponentiations. Pair each even index with the odd index right after it: a pair contributes 5 · 4 = 20 choices, there are n / 2 complete pairs, and an odd n leaves one unpaired even index worth a factor 5.

static long optimalPaired(long n) {
    long pairs = n / 2;
    long result = modPow(20, pairs);
    if (n % 2 == 1) result = result * 5 % MOD;
    return result;
}

The two formulas are algebraically identical and are tested against the same expected values.

Edge cases and pitfalls