Number of Beautiful Integers in the Range

HARD

Description

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 <= 10⁹
0 < k <= 20

Approaches

Checkout 2 different approaches to solve Number of Beautiful Integers in the Range. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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:

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.
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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(log(high)) if we convert the number to a string for processing its digits. This is considered very low.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Number of Beautiful Integers in the Range. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Number of Beautiful Integers in the Range

Patterns:

MathDynamic Programming

Companies:

Infosys |