You are given positive integers low, high, and k.
A number is beautiful if it meets both of the following conditions:
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 <= 1090 < k <= 20In #2827 Number of Beautiful Integers in the Range, the task is to count integers within a given range that satisfy two conditions: the number must be divisible by k, and it must contain an equal number of even and odd digits. A brute-force check for every number in the range is inefficient for large bounds.
The optimal strategy uses Digit Dynamic Programming (Digit DP). Instead of iterating through all numbers, we process digits from most significant to least significant while tracking key state variables such as the current position, whether the number is restricted by the upper bound (tight flag), the current remainder modulo k, and the difference between the counts of even and odd digits.
Memoization helps reuse previously computed states, drastically reducing repeated work. The final answer is obtained by computing the valid count up to the upper bound and subtracting the count up to the lower bound minus one.
This approach runs efficiently with time complexity roughly proportional to the number of digits multiplied by the DP state combinations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Digit Dynamic Programming with Memoization | O(d × k × balance × states) | O(d × k × balance) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
<div class="_1l1MA">The intended solution uses Dynamic Programming.</div>
<div class="_1l1MA">Let <code> f(n) </code> denote number of beautiful integers in the range <code> [1…n] </code>, then the answer is <code> f(r) - f(l-1) </code>.</div>
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems involving Digit DP and constrained counting are common in FAANG-style interviews. While the exact question may vary, similar problems that require counting numbers with digit constraints and modular conditions appear frequently.
The optimal approach uses Digit Dynamic Programming. It processes digits one by one while tracking constraints like divisibility by k and the difference between even and odd digit counts. This avoids checking every number in the range individually.
Digit DP is ideal because the problem involves counting numbers within a range that satisfy digit-level constraints. By building numbers digit by digit and caching states, we efficiently explore all valid possibilities without brute-force enumeration.
Most implementations rely on recursion with memoization using a multidimensional DP array or hash map. The DP state typically stores digit position, tight constraint, current remainder modulo k, and the balance between even and odd digits.