Scale Engineer

Number of Beautiful Integers in the Range

Hard
#2527Time: 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.1 company
Patterns
MathDynamic Programming
Companies
Infosys

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem