# Number of Beautiful Integers in the Range
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-beautiful-integers-in-the-range)
Canonical: https://scaleengineer.com/dsa/problems/number-of-beautiful-integers-in-the-range
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
You are given positive integers `low`, `high`, and `k`.

A number is **beautiful** if it meets both of the following conditions:

* The count of even digits in the number is equal to the count of odd digits.
* The number is divisible by `k`.

Return _the number of beautiful integers in the range_ `[low, high]`.

**Example 1:**

**Input:** low = 10, high = 20, k = 3
**Output:** 2
**Explanation:** There are 2 beautiful integers in the given range: [12,18]. 
- 12 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
- 18 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
Additionally we can see that:
- 16 is not beautiful because it is not divisible by k = 3.
- 15 is not beautiful because it does not contain equal counts even and odd digits.
It can be shown that there are only 2 beautiful integers in the given range.

**Example 2:**

**Input:** low = 1, high = 10, k = 1
**Output:** 1
**Explanation:** There is 1 beautiful integer in the given range: [10].
- 10 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 1.
It can be shown that there is only 1 beautiful integer in the given range.

**Example 3:**

**Input:** low = 5, high = 5, k = 2
**Output:** 0
**Explanation:** There are 0 beautiful integers in the given range.
- 5 is not beautiful because it is not divisible by k = 2 and it does not contain equal even and odd digits.

**Constraints:**

* `0 < low <= high <= 109`
* `0 < k <= 20`

# Approaches
## Brute Force Iteration
This approach involves iterating through each number in the given range `[low, high]` and checking if it satisfies the conditions of a beautiful integer. While simple to conceptualize, its performance is inadequate for the given constraints.
**Time:** O((high - low) * log(high)). The loop runs `high - low + 1` times. Inside the loop, counting digits of a number `n` takes `O(log10(n))` time. For the given constraints where `high - low` can be up to `10^9`, this approach is too slow. · **Space:** O(log(high)) if we convert the number to a string for processing its digits. This is considered very low.
**Pros:** Simple to understand and implement.; Works correctly for small ranges.
**Cons:** Extremely inefficient for large ranges.; Guaranteed to cause a Time Limit Exceeded (TLE) error on competitive programming platforms for the given constraints.
### Explanation
The core idea is to create a loop that runs from `low` to `high`. In each iteration, we take the current number and test it against the two properties of a beautiful integer:
1.  **Equal Even/Odd Digit Counts:** We count the occurrences of even digits (0, 2, 4, 6, 8) and odd digits (1, 3, 5, 7, 9). The counts must be equal and non-zero.
2.  **Divisibility by k:** The number must be perfectly divisible by `k` (i.e., `number % k == 0`).
If a number satisfies both conditions, we increment a counter. After checking all numbers in the range, the final value of the counter is the answer.

```java
class Solution {
    private boolean isBeautiful(int n, int k) {
        if (n % k != 0) {
            return false;
        }
        int evenCount = 0;
        int oddCount = 0;
        String s = Integer.toString(n);
        for (char c : s.toCharArray()) {
            int digit = c - '0';
            if (digit % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }
        return evenCount > 0 && evenCount == oddCount;
    }

    public int numberOfBeautifulIntegers(int low, int high, int k) {
        int count = 0;
        for (int i = low; i <= high; i++) {
            if (isBeautiful(i, k)) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `beautifulCount` to 0.
- Loop through each integer `i` from `low` to `high`.
- For each `i`, check if it's beautiful:
    - First, check if `i % k == 0`. If not, continue to the next integer.
    - If divisible, count its even and odd digits. A simple way is to convert the number to a string and iterate over its characters.
    - Initialize `evenCount = 0` and `oddCount = 0`.
    - For each digit, if it's even, increment `evenCount`; otherwise, increment `oddCount`.
    - After checking all digits, if `evenCount == oddCount` and `evenCount > 0`, the number is beautiful.
- If `i` is beautiful, increment `beautifulCount`.
- After the loop finishes, return `beautifulCount`.

## Digit Dynamic Programming
This is an optimized approach that uses dynamic programming on digits to count the numbers efficiently. Instead of checking each number, we build the numbers digit by digit and count how many valid "beautiful" numbers can be formed. The problem is solved by calculating `count(high) - count(low - 1)`, where `count(n)` finds the number of beautiful integers up to `n`.
**Time:** O(D^2 * k * 10), where `D` is the number of digits in `high` (max 10) and `k` is the given divisor (max 20). The number of DP states is `D * k * (2*D)`. Each state computation involves a loop of up to 10 digits. This is highly efficient. · **Space:** O(D^2 * k) for the memoization table, where D is the number of digits in `high`. This is well within memory limits.
**Pros:** Very efficient and passes within the time limits for large constraints.; A standard and powerful technique for a wide range of digit-based counting problems.
**Cons:** Significantly more complex to understand and implement than the brute-force approach.; Requires careful handling of states, transitions, and edge cases like leading zeros and the 'tight' constraint.
### Explanation
We design a recursive function with memoization to count beautiful numbers up to a given number `N`. The function, let's call it `solve`, constructs numbers from left to right (most significant digit to least significant). The state of our recursion must track all information needed to validate the beautiful number conditions.

The state can be defined as `solve(index, rem, diff, isTight, isLeadingZero)`:
*   `index`: The current digit position we are filling.
*   `rem`: The remainder of the number formed so far modulo `k`.
*   `diff`: The difference between the count of even and odd digits (`evenCount - oddCount`). We use an offset to keep this index non-negative.
*   `isTight`: A boolean flag. If `true`, it means we are restricted to digits up to `N`'s digit at the current `index`. If we pick a smaller digit, this flag becomes `false` for subsequent recursive calls, allowing any digit from 0-9.
*   `isLeadingZero`: A boolean flag to handle cases where we are placing leading zeros. These do not contribute to the digit counts or the number's value.

The base case for the recursion is when `index` reaches the end of the number's length. We return 1 if the formed number is beautiful (`rem == 0`, `diff` corresponds to `evenCount == oddCount`, and it's not the number zero), and 0 otherwise. Memoization is used on the state `(index, rem, diff)` to store and reuse results for subproblems, drastically reducing computation.

```java
class Solution {
    private String s;
    private int k;
    private int len;
    private Integer[][][] memo;

    public int numberOfBeautifulIntegers(int low, int high, int k) {
        return count(high) - count(low - 1);
    }

    private int count(int n) {
        this.s = String.valueOf(n);
        this.k = k;
        this.len = s.length();
        // memo[index][rem][diff]
        // diff = evenCount - oddCount. Range: -len to len. Offset by len.
        this.memo = new Integer[len][k][2 * len + 1];
        return solve(0, 0, len, true, true);
    }

    private int solve(int index, int rem, int diff, boolean isTight, boolean isLeadingZero) {
        if (index == len) {
            // diff == len means evenCount == oddCount
            // !isLeadingZero means the number is not 0.
            return !isLeadingZero && diff == len && rem == 0 ? 1 : 0;
        }

        if (!isTight && !isLeadingZero && memo[index][rem][diff] != null) {
            return memo[index][rem][diff];
        }

        int ans = 0;
        int upperBound = isTight ? (s.charAt(index) - '0') : 9;

        for (int digit = 0; digit <= upperBound; digit++) {
            boolean newTight = isTight && (digit == upperBound);

            if (isLeadingZero && digit == 0) {
                ans += solve(index + 1, 0, len, newTight, true);
            } else {
                int newDiff = diff + (digit % 2 == 0 ? 1 : -1);
                int newRem = (rem * 10 + digit) % k;
                ans += solve(index + 1, newRem, newDiff, newTight, false);
            }
        }

        if (!isTight && !isLeadingZero) {
            memo[index][rem][diff] = ans;
        }

        return ans;
    }
}
```
### Algorithm
- The final answer is `count(high) - count(low - 1)`.
- The `count(n)` function converts `n` to a string `s` and calls a recursive helper `solve`.
- The `solve(index, rem, diff, isTight, isLeadingZero)` function works as follows:
    - **Base Case:** If `index == s.length()`, return 1 if `rem == 0`, `diff` indicates equal counts, and the number is not zero (`!isLeadingZero`). Otherwise, return 0.
    - **Memoization:** Check if the state `(index, rem, diff)` has been computed before (only when `isTight` and `isLeadingZero` are false) and return the stored value.
    - **Recursion:**
        - Determine the upper bound for the current digit (either `s[index]` or 9, based on `isTight`).
        - Iterate through all valid digits from 0 to the upper bound.
        - For each digit, update the state (`rem`, `diff`, `isTight`, `isLeadingZero`) and make a recursive call to `solve` for `index + 1`.
        - Sum the results from all recursive calls.
    - **Memoize:** Store the calculated sum in the memoization table before returning.

# Solutions
### Java

```java
class Solution {
private
  String s;
private
  int k;
private
  Integer[][][] f = new Integer[11][21][21];
public
  int numberOfBeautifulIntegers(int low, int high, int k) {
    this.k = k;
    s = String.valueOf(high);
    int a = dfs(0, 0, 10, true, true);
    s = String.valueOf(low - 1);
    f = new Integer[11][21][21];
    int b = dfs(0, 0, 10, true, true);
    return a - b;
  }
private
  int dfs(int pos, int mod, int diff, boolean lead, boolean limit) {
    if (pos >= s.length()) {
      return mod == 0 && diff == 10 ? 1 : 0;
    }
    if (!lead && !limit && f[pos][mod][diff] != null) {
      return f[pos][mod][diff];
    }
    int ans = 0;
    int up = limit ? s.charAt(pos) - '0' : 9;
    for (int i = 0; i <= up; ++i) {
      if (i == 0 && lead) {
        ans += dfs(pos + 1, mod, diff, true, limit && i == up);
      } else {
        int nxt = diff + (i % 2 == 1 ? 1 : -1);
        ans += dfs(pos + 1, (mod * 10 + i) % k, nxt, false, limit && i == up);
      }
    }
    if (!lead && !limit) {
      f[pos][mod][diff] = ans;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfBeautifulIntegers(int low, int high, int k) {
    int f[11][21][21];
    memset(f, -1, sizeof(f));
    string s = to_string(high);
    function<int(int, int, int, bool, bool)> dfs = [&](int pos, int mod,
                                                       int diff, bool lead,
                                                       bool limit) {
      if (pos >= s.size()) {
        return mod == 0 && diff == 10 ? 1 : 0;
      }
      if (!lead && !limit && f[pos][mod][diff] != -1) {
        return f[pos][mod][diff];
      }
      int ans = 0;
      int up = limit ? s[pos] - '0' : 9;
      for (int i = 0; i <= up; ++i) {
        if (i == 0 && lead) {
          ans += dfs(pos + 1, mod, diff, true, limit && i == up);
        } else {
          int nxt = diff + (i % 2 == 1 ? 1 : -1);
          ans += dfs(pos + 1, (mod * 10 + i) % k, nxt, false, limit && i == up);
        }
      }
      if (!lead && !limit) {
        f[pos][mod][diff] = ans;
      }
      return ans;
    };
    int a = dfs(0, 0, 10, true, true);
    memset(f, -1, sizeof(f));
    s = to_string(low - 1);
    int b = dfs(0, 0, 10, true, true);
    return a - b;
  }
};

```

### Python

```python
class Solution:
    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int: @ cache def dfs(pos: int, mod: int, diff: int, lead: int, limit: int) -> int: if pos >= len(s): return mod == 0 and diff == 10 up = int(s[pos]) if limit else 9 ans = 0 for i in range(up + 1): if i == 0 and lead: ans += dfs(pos + 1, mod, diff, 1, limit and i == up) else: nxt = diff + (1 if i % 2 == 1 else - 1) ans += dfs(pos + 1, (mod * 10 + i) % k, nxt, 0, limit and i == up) return ans s = str(high) a = dfs(0, 0, 10, 1, 1) dfs . cache_clear() s = str(low - 1) b = dfs(0, 0, 10, 1, 1) return a - b

```