# Count Good Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-good-numbers)
Canonical: https://scaleengineer.com/dsa/problems/count-good-numbers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
---
## 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 (`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** `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`

# Approaches
## Naive Iteration (Time Limit Exceeded)
This approach directly translates the problem's combinatorial logic into code. We first determine the number of even and odd positions in a string of length `n`. Then, we calculate the total number of permutations by raising the number of choices for each position type (5 for even, 4 for odd) to the power of their respective counts. The exponentiation is performed using a simple loop. While straightforward, this method is too slow for the given constraints.
**Time:** O(n). The `naivePower` function has a time complexity of O(exponent). Since the exponents are proportional to `n`, the overall complexity is O(n). · **Space:** O(1). The algorithm uses a constant amount of extra space.
**Pros:** Very simple to understand and implement.
**Cons:** Extremely inefficient for large values of `n`.; Will cause a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
The problem asks for the number of 'good' strings of length `n`. A good string has even digits (0, 2, 4, 6, 8) at even indices and prime digits (2, 3, 5, 7) at odd indices.

1.  **Count Positions**: For a string of length `n`, there are `(n + 1) / 2` even indices and `n / 2` odd indices.
2.  **Count Choices**: There are 5 choices for each even position and 4 choices for each odd position.
3.  **Total Permutations**: The total number of good strings is `(5 ^ ((n + 1) / 2)) * (4 ^ (n / 2))`, all calculated modulo `10^9 + 7`.

The naive approach implements a power function that uses a simple loop to perform multiplication. 

```java
private long naivePower(long base, long exp) {
    long res = 1;
    long MOD = 1_000_000_007;
    base %= MOD;
    for (long i = 0; i < exp; i++) {
        res = (res * base) % MOD;
    }
    return res;
}

public int countGoodNumbers(long n) {
    long MOD = 1_000_000_007;
    long evenCount = (n + 1) / 2;
    long oddCount = n / 2;

    long evenPermutations = naivePower(5, evenCount);
    long oddPermutations = naivePower(4, oddCount);

    return (int)((evenPermutations * oddPermutations) % MOD);
}
```

This approach is too slow because the exponent `exp` can be as large as `10^15`. A loop running that many times will result in a 'Time Limit Exceeded' error.
### Algorithm
- Calculate the number of even indices: `evenCount = (n + 1) / 2`.
- Calculate the number of odd indices: `oddCount = n / 2`.
- Define a function `naivePower(base, exp)` that computes `(base^exp) % MOD` using a simple loop that iterates `exp` times.
- In each iteration of the loop, multiply the running result by `base` and take the modulo.
- Calculate `term1 = naivePower(5, evenCount)`.
- Calculate `term2 = naivePower(4, oddCount)`.
- The final result is `(term1 * term2) % MOD`.

## Binary Exponentiation (Fast Powering)
This is the optimal approach for this problem. It leverages a mathematical technique called Binary Exponentiation (or Exponentiation by Squaring) to calculate powers in logarithmic time. The core idea is to reduce the exponent by half at each step, drastically cutting down the number of required multiplications. This efficiency makes it possible to handle the large exponents derived from `n` up to `10^15`.
**Time:** O(log n). The `power` function runs in time proportional to the number of bits in the exponent, which is `log(exponent)`. Since the exponents are proportional to `n`, the overall complexity is O(log n). · **Space:** O(1). The iterative implementation of binary exponentiation uses a constant amount of extra space.
**Pros:** Extremely efficient, with logarithmic time complexity.; The standard solution for modular exponentiation problems.; Easily handles the large constraints on `n`.
**Cons:** Slightly more complex to understand initially compared to the naive loop.
### Explanation
The combinatorial formula remains the same: `Total = (5 ^ evenCount) * (4 ^ oddCount) % MOD`. The challenge is computing `a^b % MOD` where `b` is large.

Binary Exponentiation solves this efficiently. It is based on the following properties:
- If the exponent `b` is even, `a^b = (a^2)^(b/2)`.
- If the exponent `b` is odd, `a^b = a * a^(b-1) = a * (a^2)^((b-1)/2)`.

By repeatedly applying these rules, we can compute the power in `O(log b)` time. We can implement this both recursively and iteratively. The iterative approach is generally preferred as it avoids potential stack overflow and uses `O(1)` space.

Here is the implementation using an iterative fast power function:

```java
class Solution {
    long MOD = 1_000_000_007;

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            exp /= 2; // or exp >>= 1;
        }
        return res;
    }

    public int countGoodNumbers(long n) {
        long evenCount = (n + 1) / 2;
        long oddCount = n / 2;

        long evenPermutations = power(5, evenCount);
        long oddPermutations = power(4, oddCount);

        return (int)((evenPermutations * oddPermutations) % MOD);
    }
}
```

This algorithm is highly efficient and is the standard way to solve problems involving modular exponentiation with large powers.
### Algorithm
- Calculate the number of even indices: `evenCount = (n + 1) / 2`.
- Calculate the number of odd indices: `oddCount = n / 2`.
- Implement an efficient `power(base, exp)` function using the binary exponentiation algorithm.
- Inside the `power` function, iterate while `exp > 0`. In each step, if `exp` is odd, multiply the result by the current `base`. Then, square the `base` and halve the `exp`.
- Calculate `term1 = power(5, evenCount)`.
- Calculate `term2 = power(4, oddCount)`.
- The final result is `(term1 * term2) % MOD`.

# Solutions
### Java

```java
class Solution {
private
  int mod = 1000000007;
public
  int countGoodNumbers(long n) {
    return (int)(myPow(5, (n + 1) >> 1) * myPow(4, n >> 1) % mod);
  }
private
  long myPow(long x, long n) {
    long res = 1;
    while (n != 0) {
      if ((n & 1) == 1) {
        res = res * x % mod;
      }
      x = x * x % mod;
      n >>= 1;
    }
    return res;
  }
}

```

### CPP

```cpp
int MOD = 1000000007 ; class Solution { public: int countGoodNumbers ( long long n ) { return ( int ) ( myPow ( 5 , ( n + 1 ) >> 1 ) * myPow ( 4 , n >> 1 ) % MOD ); } private: long long myPow ( long long x , long long n ) { long long res = 1 ; while ( n ) { if (( n & 1 ) == 1 ) { res = res * x % MOD ; } x = x * x % MOD ; n >>= 1 ; } return res ; } };
```

### Python

```python
class Solution:
    def countGoodNumbers(self, n: int) -> int: mod = 10 ** 9 + 7 def myPow(x, n): res = 1 while n: if (n & 1) == 1: res = res * x % mod x = x * x % mod n >>= 1 return res return myPow(5, (n + 1) >> 1) * myPow(4, n >> 1) % mod

```