LeetCode 2827 - Number of Beautiful Integers in the Range

LeetCode Problem 2827

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming

Solution

Problem Understanding

The problem asks us to count how many integers within the inclusive range [low, high] satisfy two independent conditions.

The first condition is based on the digits of the number. A number is considered beautiful only if it contains an equal number of even digits and odd digits. For example, 12 is valid because it has one even digit (2) and one odd digit (1). However, 123 is invalid because it contains two odd digits and one even digit.

The second condition is arithmetic. The number must also be divisible by k.

We are given three integers:

• low, the lower bound of the range
• high, the upper bound of the range
• k, the divisor

We must return the total count of integers in [low, high] that satisfy both requirements.

The constraints are important:

• high can be as large as 10^9
• k can be at most 20

Since the range size itself can potentially approach one billion numbers, iterating through every integer and checking its digits individually would be far too slow. This immediately suggests that we need a more advanced counting technique.

Another important observation is that a number can only have an equal count of even and odd digits if its total number of digits is even. Any odd-length number is automatically invalid.

There are also several edge cases worth noticing early:

• Single digit numbers can never be beautiful because they contain either one even digit or one odd digit, never both equally.
• Leading zeros must not affect the even/odd digit counts.
• We must carefully handle divisibility while constructing numbers digit by digit.
• The range boundaries are inclusive, so we typically compute:

count(high) - count(low - 1)

This type of problem strongly suggests a Digit DP solution.

Approaches

Brute Force Approach

The most straightforward solution is to iterate through every integer from low to high.

For each number:

1. Extract its digits.
2. Count how many digits are even.
3. Count how many digits are odd.
4. Check whether the counts are equal.
5. Check whether the number is divisible by k.

If both conditions hold, increment the answer.

This approach is correct because it explicitly verifies every requirement for every number in the range.

However, the performance is unacceptable for the given constraints. In the worst case, the range size can approach 10^9, making direct iteration impossible within time limits.

Optimal Approach, Digit DP

The key insight is that we do not need to enumerate every number individually.

Instead, we can count valid numbers digit by digit using Dynamic Programming over digits, commonly called Digit DP.

Digit DP works well whenever:

• We are counting numbers within a range.
• The property depends on the digits of the number.
• The property can be built incrementally.

In this problem, both conditions can be tracked incrementally:

• We can maintain the difference between even and odd digit counts.
• We can maintain the current remainder modulo k.

While constructing a number from left to right:

• Adding a digit updates the parity balance.
• Adding a digit updates the modulo remainder.

We also maintain standard Digit DP states:

• Current position
• Whether we are still restricted by the upper bound
• Whether the number has started yet, to avoid counting leading zeros incorrectly

Using memoization, the number of distinct states remains small, making the solution efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((high - low + 1) × log(high))	O(1)	Checks every number individually
Optimal	O(digits × k × balance × states)	O(digits × k × balance × states)	Uses Digit DP with memoization

Algorithm Walkthrough

Step 1: Convert Range Counting into Prefix Counting

Instead of directly counting beautiful integers inside [low, high], we define a helper function:

count(x)

This function returns the number of beautiful integers in [0, x].

Then the final answer becomes:

count(high) - count(low - 1)

This is a standard technique for range counting problems.

Step 2: Process Digits Left to Right

We convert the number x into a string so we can process each digit position individually.

At every position, we decide which digit to place.

For example, if x = 527, we recursively choose:

• First digit
• Second digit
• Third digit

while respecting the upper bound.

Step 3: Define DP State

Our recursive DP function tracks:

1. pos

The current digit index we are filling. 2. balance

The difference:

even_count - odd_count

3. mod

Current remainder modulo k. 4. started

Whether we have placed a non-leading-zero digit yet. 5. tight

Whether the current prefix is still equal to the upper bound prefix.

Step 4: Handle Leading Zeros Carefully

Leading zeros are special.

Before the number starts:

• Digits should not affect parity counts.
• Digits should not affect modulo state.

This prevents numbers like "0012" from incorrectly counting zeros as even digits.

Step 5: Transition Between States

For every possible digit choice:

• Update tight constraint
• Update modulo:

new_mod = (mod * 10 + digit) % k

• Update parity balance:

• even digit → balance + 1

• odd digit → balance - 1

Step 6: Define Base Case

When all positions are processed:

• The number must have started.
• balance must equal 0.
• mod must equal 0.

If all conditions hold, return 1.

Otherwise return 0.

Step 7: Memoize Results

Many recursive states repeat.

Memoization ensures each unique state is computed only once.

This dramatically reduces complexity.

Why it works

The DP explores every valid number exactly once while preserving all necessary information about the partially constructed number.

The balance state guarantees that we know whether the final number contains equal counts of even and odd digits. The mod state guarantees divisibility by k. The tight flag ensures we never exceed the upper bound, and the started flag prevents leading zeros from corrupting the digit counts.

Because every possible digit combination is explored systematically and every valid completed state contributes exactly one count, the algorithm correctly computes the number of beautiful integers.

Python Solution

from functools import lru_cache

class Solution:
    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
        
        def count_beautiful(limit: int) -> int:
            if limit <= 0:
                return 0

            digits = str(limit)
            n = len(digits)

            @lru_cache(None)
            def dp(pos: int,
                   balance: int,
                   mod: int,
                   started: bool,
                   tight: bool) -> int:

                if pos == n:
                    return int(started and balance == 0 and mod == 0)

                upper = int(digits[pos]) if tight else 9
                total = 0

                for digit in range(upper + 1):
                    new_tight = tight and (digit == upper)

                    if not started and digit == 0:
                        total += dp(
                            pos + 1,
                            balance,
                            mod,
                            False,
                            new_tight
                        )
                    else:
                        if digit % 2 == 0:
                            new_balance = balance + 1
                        else:
                            new_balance = balance - 1

                        new_mod = (mod * 10 + digit) % k

                        total += dp(
                            pos + 1,
                            new_balance,
                            new_mod,
                            True,
                            new_tight
                        )

                return total

            return dp(0, 0, 0, False, True)

        return count_beautiful(high) - count_beautiful(low - 1)

The implementation follows the Digit DP structure described earlier.

The outer helper function count_beautiful(limit) computes how many beautiful integers exist in the range [0, limit].

The recursive function dp(...) processes the number digit by digit.

The balance variable stores:

even_digits - odd_digits

Whenever we place an even digit, we increment the balance. Whenever we place an odd digit, we decrement it.

The modulo state is updated incrementally using the standard base-10 transition:

new_mod = (mod * 10 + digit) % k

The started flag prevents leading zeros from being treated as actual digits.

Memoization with @lru_cache ensures repeated states are reused efficiently.

Finally, the range result is computed using:

count(high) - count(low - 1)

which converts a range query into two prefix queries.

Go Solution

package main

import "strconv"

func numberOfBeautifulIntegers(low int, high int, k int) int {

	countBeautiful := func(limit int) int {
		if limit <= 0 {
			return 0
		}

		digits := strconv.Itoa(limit)
		n := len(digits)

		type State struct {
			pos     int
			balance int
			mod     int
			started bool
			tight   bool
		}

		memo := make(map[State]int)

		var dfs func(int, int, int, bool, bool) int

		dfs = func(pos int,
			balance int,
			mod int,
			started bool,
			tight bool) int {

			if pos == n {
				if started && balance == 0 && mod == 0 {
					return 1
				}
				return 0
			}

			state := State{
				pos,
				balance,
				mod,
				started,
				tight,
			}

			if val, exists := memo[state]; exists {
				return val
			}

			upper := 9
			if tight {
				upper = int(digits[pos] - '0')
			}

			total := 0

			for digit := 0; digit <= upper; digit++ {
				newTight := tight && (digit == upper)

				if !started && digit == 0 {
					total += dfs(
						pos+1,
						balance,
						mod,
						false,
						newTight,
					)
				} else {
					newBalance := balance

					if digit%2 == 0 {
						newBalance++
					} else {
						newBalance--
					}

					newMod := (mod*10 + digit) % k

					total += dfs(
						pos+1,
						newBalance,
						newMod,
						true,
						newTight,
					)
				}
			}

			memo[state] = total
			return total
		}

		return dfs(0, 0, 0, false, true)
	}

	return countBeautiful(high) - countBeautiful(low-1)
}

The Go implementation mirrors the Python logic closely.

Since Go does not provide built in memoization decorators like Python's lru_cache, we explicitly store DP results in a hash map keyed by a custom State struct.

Go also requires explicit recursive function declarations using function variables.

The balance value can become negative, but Go integers naturally support this without additional handling.

Integer overflow is not a concern because the result comfortably fits within standard integer limits for the given constraints.

Worked Examples

Example 1

low = 10
high = 20
k = 3

We compute:

count(20) - count(9)

Valid Numbers in Range

Number	Even Digits	Odd Digits	Divisible by 3	Beautiful
10	1	1	No	No
11	0	2	No	No
12	1	1	Yes	Yes
13	0	2	No	No
14	1	1	No	No
15	0	2	Yes	No
16	1	1	No	No
17	0	2	No	No
18	1	1	Yes	Yes
19	0	2	No	No
20	2	0	No	No

Final answer:

2

DP Trace for Number 12

Position	Digit	Balance Change	New Balance	Modulo
0	1	odd → -1	-1	1
1	2	even → +1	0	0

Final state:

balance = 0
mod = 0

So 12 is counted.

Example 2

low = 1
high = 10
k = 1

Every number is divisible by 1, so only parity balance matters.

Single digit numbers cannot have equal counts of even and odd digits.

Only 10 works.

Number	Even Digits	Odd Digits	Beautiful
1-9	unequal	unequal	No
10	1	1	Yes

Final answer:

1

Example 3

low = 5
high = 5
k = 2

Only one number exists in the range.

Number	Even Digits	Odd Digits	Divisible by 2	Beautiful
5	0	1	No	No

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d × k × b × 10 × 2 × 2)	DP explores all digit states
Space	O(d × k × b × 2 × 2)	Memoization table size

Where:

• d is the number of digits, at most 10
• b is the balance range, at most [-10, 10]

Since both values are very small, the algorithm runs efficiently within limits.

The recursion depth never exceeds the number of digits, and memoization prevents exponential recomputation.

Test Cases

sol = Solution()

assert sol.numberOfBeautifulIntegers(10, 20, 3) == 2
# Basic example from statement

assert sol.numberOfBeautifulIntegers(1, 10, 1) == 1
# Only 10 qualifies

assert sol.numberOfBeautifulIntegers(5, 5, 2) == 0
# Single invalid number

assert sol.numberOfBeautifulIntegers(10, 10, 10) == 1
# Exact boundary match

assert sol.numberOfBeautifulIntegers(11, 11, 1) == 0
# Equal parity condition fails

assert sol.numberOfBeautifulIntegers(12, 12, 3) == 1
# Single valid beautiful integer

assert sol.numberOfBeautifulIntegers(1, 99, 1) == 45
# All two digit numbers with one even and one odd digit

assert sol.numberOfBeautifulIntegers(100, 200, 2) >= 0
# General medium range sanity test

assert sol.numberOfBeautifulIntegers(1, 1000000000, 20) >= 0
# Maximum constraint stress test

assert sol.numberOfBeautifulIntegers(22, 22, 11) == 0
# Two even digits, unequal counts

assert sol.numberOfBeautifulIntegers(21, 21, 3) == 1
# One odd and one even digit, divisible by 3

Test	Why
(10, 20, 3)	Verifies official example
(1, 10, 1)	Tests single digit behavior
(5, 5, 2)	Tests single element range
(10, 10, 10)	Exact valid boundary
(11, 11, 1)	Invalid parity counts
(12, 12, 3)	Single valid number
(1, 99, 1)	Validates many two digit combinations
(100, 200, 2)	Medium sized interval
(1, 1000000000, 20)	Maximum constraint stress
(22, 22, 11)	All even digits case
(21, 21, 3)	Small valid example

Edge Cases

Single Digit Numbers

A single digit number can never contain equal counts of even and odd digits. This is easy to overlook because divisibility alone may pass.

The implementation handles this naturally because the final balance can never become zero after processing exactly one non-leading digit.

Leading Zeros

Leading zeros are a common source of bugs in Digit DP problems.

For example, when representing 12 as "0012", the zeros should not count as even digits.

The started flag ensures leading zeros do not modify either the parity balance or the modulo state until the first nonzero digit appears.

Numbers with Odd Digit Length

Any number with an odd number of digits can never have equal even and odd counts.

The DP does not explicitly filter these numbers beforehand. Instead, such numbers automatically fail because the final balance cannot return to zero after an odd number of digit insertions.

This implicit handling keeps the implementation simpler and less error prone.

Lower Bound Equal to 1

When computing:

count(low - 1)

we may evaluate:

count(0)

The implementation safely returns 0 immediately for nonpositive limits, avoiding invalid recursion or incorrect counting of zero itself.