#2827

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Beautiful Integers in the Range

Count all integers in a given range that have equal even and odd digits and are divisible by k using DP.

Problem Statement

You are given three positive integers low, high, and k. A number is considered beautiful if it has an equal number of even and odd digits and is divisible by k.

Return the total number of beautiful integers within the inclusive range [low, high]. For example, check all numbers between low and high, and count only those satisfying both digit balance and divisibility by k.

Examples

Example 1

Input: low = 10, high = 20, k = 3

Output: 2

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

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

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

Solution Approach

Define DP State

Use a dynamic programming state dp(pos, tight, evenCount, oddCount, mod) where pos is the current digit position, tight limits the prefix to the upper bound, evenCount and oddCount track parity counts, and mod stores remainder modulo k.

Implement Recursive Transition

Recursively explore each digit from 0 to 9. Update evenCount or oddCount based on digit parity, compute new modulo k, and propagate tight constraint. Memoize results to avoid recomputation and ensure performance across large ranges.

Compute Range and Return Result

Calculate beautiful numbers from 1 to high and subtract count from 1 to low-1 to get the final count in [low, high]. Ensure base case checks for evenCount == oddCount and mod == 0 before counting a number as beautiful.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on the number of digits and k. The DP table has dimensions proportional to number of digits, parity difference, and modulo k, resulting in manageable memory and polynomial runtime relative to digit length and k.

What Interviewers Usually Probe

Candidate correctly identifies digit DP as a viable approach.
Shows understanding of state transitions for even/odd counts and modulo k.
Uses memoization effectively to handle large ranges up to 10^9.

Common Pitfalls or Variants

Common pitfalls

Confusing digit parity counting or forgetting to track both even and odd digits.
Neglecting the modulo k constraint when updating DP states.
Failing to handle tight constraint correctly, causing overcounting beyond high.

Follow-up variants

Count numbers with more even digits than odd digits divisible by k.
Find numbers with alternating odd and even digits within a range divisible by k.
Compute numbers with exact digit sum divisible by k and balanced parity.

FAQ

What is a beautiful integer in this problem?

A beautiful integer has equal numbers of even and odd digits and is divisible by k.

Which dynamic programming pattern is used here?

State transition dynamic programming tracks digit positions, parity counts, and modulo to count valid numbers.

Can this approach handle large ranges efficiently?

Yes, memoization ensures performance even when high is up to 10^9 by avoiding redundant calculations.

How do I initialize the DP table?

Start with position 0, tight constraint true, evenCount and oddCount 0, and mod 0, then recursively fill states.

What should I watch out for in implementation?

Avoid miscounting parity digits, ensure modulo updates correctly, and respect tight bounds to prevent overcounting.

terminal

Solution

Solution 1: Digit DP

We notice that the problem is asking for the number of beautiful integers in the interval $[low, high]$. For such an interval $[l,..r]$ problem, we can usually consider transforming it into finding the answers for $[1, r]$ and $[1, l-1]$, and then subtracting the latter from the former. Moreover, the problem only involves the relationship between different digits, not the specific values, so we can consider using Digit DP to solve it.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

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

Continue Practicing

#2851 string transformation #2867 count valid paths in a tree #2750 ways to split array into good subarrays