LeetCode 3791 - Number of Balanced Integers in a Range

Difficulty: 🔴 Hard
Topics: Dynamic Programming

Solution

Here is the full, detailed technical solution guide for LeetCode 3791 - Number of Balanced Integers in a Range, following your requested structure.

Problem Understanding

The problem asks us to count all integers between low and high inclusive that are balanced. An integer is defined as balanced if it meets two conditions. First, it must have at least two digits. Second, the sum of its digits in even positions must equal the sum of its digits in odd positions, where the leftmost digit is considered position 1.

The inputs low and high are integers in the range [1, 10^15]. Because of this large range, a naive approach that iterates through every integer would be far too slow. The expected output is the count of all integers in [low, high] that satisfy the balanced condition.

Key constraints and observations include:

Single-digit numbers cannot be balanced.
Large numbers up to 10^15 make brute-force enumeration infeasible.
Position counting starts from the leftmost digit, so the parity of a digit depends on its position in the number rather than its numeric value.
Edge cases include ranges that do not contain any two-digit numbers or ranges where all numbers are single-digit.

Approaches

Brute Force Approach

The brute-force approach would iterate from low to high. For each number, convert it to a string or array of digits, then sum the digits in odd positions and even positions separately. Compare the sums; if they match and the number has at least two digits, increment the count.

While correct, this approach is far too slow for large inputs. With high up to 10^15, iterating linearly is infeasible.

Optimal Approach: Digit Dynamic Programming (Digit DP)

The key insight is to use Digit DP, a technique that allows counting numbers with specific digit constraints efficiently without generating each number.

We define a DP state that captures:

The current position in the number.
The difference between the sum of odd-position digits and even-position digits.
Whether the number built so far is tight (equal to the prefix of high) to handle upper bounds correctly.
Whether the number has started (to skip leading zeros).

By recursively exploring valid digits at each position and memoizing intermediate results, we can compute the number of balanced integers efficiently for any range [low, high].

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(high - low)	O(log(high))	Iterates every number and sums digits, too slow for large ranges
Digit DP (Optimal)	O(length^2 * sum_diff)	O(length * sum_diff * 2)	Uses memoization over position, difference, and tight/started flags

length is the number of digits in high (up to 16), and sum_diff is the range of possible differences between odd and even sums (up to 9 * length).

Algorithm Walkthrough

Convert the number to a string to access its digits easily.
Define a recursive function dp(pos, diff, tight, started) where:

pos is the current digit index.
diff is odd_sum - even_sum.
tight is a boolean indicating if the number prefix is bounded by the original number.
started is a boolean indicating if we have placed any non-zero digit yet.

At each position, iterate over digits from 0 to the current upper limit (9 or digit at pos if tight).
For each digit, compute the new difference:

If started is False, skip the digit if it is 0.
Otherwise, update diff by adding/subtracting the digit depending on the position parity.

Recurse to the next position with updated diff, tight, and started.
Base case: when pos equals the length of the number, return 1 if diff is zero and started is True (number has at least two digits).
Use memoization to store results for (pos, diff, tight, started) to avoid recomputation.
To handle a range [low, high], compute count(high) - count(low - 1).

Why it works: This algorithm systematically counts all valid numbers that satisfy the balanced condition without generating each number explicitly. Memoization ensures each state is computed once, and the recursive transitions preserve the invariant that diff always represents the difference between odd and even digit sums of the number built so far.

Python Solution

class Solution:
    def countBalanced(self, low: int, high: int) -> int:
        from functools import lru_cache

        def count(n: int) -> int:
            digits = list(map(int, str(n)))

            @lru_cache(None)
            def dp(pos: int, diff: int, tight: bool, started: bool) -> int:
                if pos == len(digits):
                    return int(started and diff == 0)
                res = 0
                upper = digits[pos] if tight else 9
                for d in range(0, upper + 1):
                    new_started = started or d != 0
                    new_tight = tight and (d == upper)
                    if new_started:
                        parity = (pos + 1) % 2  # leftmost digit is position 1
                        new_diff = diff + d if parity == 1 else diff - d
                        res += dp(pos + 1, new_diff, new_tight, new_started)
                    else:
                        res += dp(pos + 1, diff, new_tight, new_started)
                return res

            return dp(0, 0, True, False)

        return count(high) - count(low - 1)

Explanation: We define a helper count(n) that computes the number of balanced integers up to n using digit DP. The main function returns count(high) - count(low - 1) to handle ranges correctly. The DP state uses lru_cache for memoization, and we carefully manage the parity of digit positions for odd/even sums.

Go Solution

func countBalanced(low int64, high int64) int64 {
    var digits []int
    var dp func(pos int, diff int, tight bool, started bool) int64
    var memo map[[4]int64]int64

    count := func(n int64) int64 {
        digits = []int{}
        for n > 0 {
            digits = append([]int{int(n % 10)}, digits...)
            n /= 10
        }
        memo = make(map[[4]int64]int64)
        var helper func(pos int, diff int, tight bool, started bool) int64
        helper = func(pos int, diff int, tight bool, started bool) int64 {
            if pos == len(digits) {
                if started && diff == 0 {
                    return 1
                }
                return 0
            }
            key := [4]int64{int64(pos), int64(diff + 500), 0, 0} // diff offset
            if tight {
                key[2] = 1
            }
            if started {
                key[3] = 1
            }
            if val, ok := memo[key]; ok {
                return val
            }
            var res int64 = 0
            upper := 9
            if tight {
                upper = digits[pos]
            }
            for d := 0; d <= upper; d++ {
                newStarted := started || d != 0
                newTight := tight && d == upper
                if newStarted {
                    parity := (pos + 1) % 2
                    newDiff := diff
                    if parity == 1 {
                        newDiff += d
                    } else {
                        newDiff -= d
                    }
                    res += helper(pos+1, newDiff, newTight, newStarted)
                } else {
                    res += helper(pos+1, diff, newTight, newStarted)
                }
            }
            memo[key] = res
            return res
        }
        return helper(0, 0, true, false)
    }

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

Go differences: We cannot use Python’s lru_cache, so we implement a memoization map keyed by a fixed-length array. We offset diff in the key to avoid negative indices. Otherwise, the logic mirrors the Python solution.

Worked Examples

Example 1: low = 1, high = 100

Compute count(100):
Two-digit numbers 11, 22, 33, 44, 55, 66, 77, 88, 99 are balanced.
Compute count(0):
No numbers, returns 0.
Result: 9

Example 2: low = 120, high = 129

Compute count(129):
Only 121 is balanced (odd positions sum = 1+1=2, even position sum = 2)
Compute count(119):
Only numbers below 120 are balanced: 11, 22, ..., 99
Result: 1

Example 3: low = 1234, high = 1234

1234: odd sum = 1