3791. Number of Balanced Integers in a Range

HardDynamic Programming

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given two integers low and high.

An integer is called balanced if it satisfies both of the following conditions:

It contains at least two digits.
The sum of digits at even positions is equal to the sum of digits at odd positions (the leftmost digit has position 1).

Your task is to return an integer representing the number of balanced integers in the range [low, high] (both inclusive).

For example, consider the number 1230. Counting positions from the left starting at 1:

Digits at odd positions (positions 1 and 3) are 1 and 3, with a sum of 1 + 3 = 4.
Digits at even positions (positions 2 and 4) are 2 and 0, with a sum of 2 + 0 = 2.

Since 4 != 2, the number 1230 is not balanced.

In contrast, the number 11 has the digit 1 at position 1 (odd) and the digit 1 at position 2 (even). Both sums are equal to 1, and it contains at least two digits, so 11 is balanced.

You need to count how many such balanced integers exist within the given inclusive range from low to high.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

Counting balanced integers in a large range requires digit DP to count qualifying numbers without enumerating each one.

Open in Flowchart

Intuition

The range [low, high] can be extremely large, so iterating through every integer one by one and checking whether it is balanced is not feasible. We need a smarter way to count the qualifying numbers without examining each one individually.

The key observation is that the "balanced" condition only depends on the digits of a number and where those digits sit (odd or even positions). Whether a number is balanced is determined solely by the digit composition, not by the number's overall magnitude. This naturally points us toward counting by constructing numbers digit by digit, a technique known as Digit DP.

To handle the range [low, high], we use a common trick: instead of counting directly within the range, we count the number of balanced integers in [1, x] using a helper, then apply the difference. If count(x) gives the number of balanced integers from 1 to x, then the answer for [low, high] is simply count(high) - count(low - 1). This converts a two-sided range problem into two prefix-counting problems, which are much easier to reason about.

Now, when building a number digit by digit from left to right, we need to track just enough information to know whether the final number is balanced:

The position pos we are currently filling, so we know whether it is an odd or even position.
A running value diff, representing the difference between the sum of digits placed at odd positions and the sum at even positions. When we place digit i at an even-indexed position (in the code, pos % 2 == 0), we add i; otherwise, we subtract i. At the end, a number is balanced exactly when diff == 0.
A flag lim, indicating whether the digits chosen so far exactly match the prefix of the upper bound. If lim is true, the next digit cannot exceed the corresponding digit of the bound; otherwise, we are free to choose any digit from 0 to 9.

By recursing over every valid digit choice and summing up the results, we count all numbers that lead to a balanced state. Since the same (pos, diff, lim) state can be reached through many different digit prefixes, we apply memoization to cache results and avoid recomputing the same subproblems repeatedly.

Finally, because balanced numbers must have at least two digits, any number below 11 cannot qualify. So if high < 11, the answer is immediately 0, and we clamp low up to at least 11 before counting. This handles the minimum-digit constraint cleanly without complicating the core DP logic.

Pattern Learn more about Dynamic Programming patterns.

Solution Approach

Solution 1: Digit DP

First, if high < 11, there are no balanced integers in the range (because a balanced integer must have at least two digits), so we directly return 0. Otherwise, we update low to max(low, 11) to ensure we only consider numbers with at least two digits.

Then we design a function dfs(pos, diff, lim), which represents processing the pos-th digit of the number, where diff is the difference between the sum of digits at odd positions and the sum of digits at even positions, and lim indicates whether the current digit is constrained by the upper bound. The function returns the number of balanced integers that can be constructed from the current state.

The execution logic of the function is as follows:

If pos exceeds the length of the number, it means all digits have been processed. If diff == 0, the current number is a balanced integer, return 1; otherwise, return 0.
Calculate the upper bound up for the current digit. If constrained (lim is true), it equals the current digit of the number int(num[pos]); otherwise, it is 9.
Iterate through all possible digits i from 0 to up for the current position. For each digit i, recursively call dfs(pos + 1, diff + i * (1 if pos % 2 == 0 else -1), lim and i == up), and accumulate the results. Here, when pos % 2 == 0 we add i to diff, otherwise we subtract i, so that a final diff of 0 exactly corresponds to a balanced number.
Return the accumulated result.

We first calculate the number of balanced integers a in the range [1, low - 1] by setting num = str(low - 1) and calling dfs(0, 0, True). Then we clear the cache with dfs.cache_clear() (since num changes and the cached states are no longer valid), set num = str(high), and calculate the number of balanced integers b in the range [1, high]. Finally, we return b - a, which gives the count of balanced integers in [low, high].

To avoid redundant calculations, we use memoization (via the @cache decorator) to store previously computed states, since the same (pos, diff, lim) state can be reached through many different digit prefixes.

The time complexity is O(D * S * 10), where D is the number of digits and S is the range of possible diff values, and the space complexity is O(D * S) for the memoization cache.

Example Walkthrough

Let's trace through a small example with low = 10 and high = 13. We expect the answer to be 1, because among 10, 11, 12, 13, only 11 is balanced (digit 1 at position 1 equals digit 1 at position 2).

Step 1: Handle the minimum-digit constraint

Since high = 13 is not less than 11, we proceed. We update low = max(10, 11) = 11. This means we only need to consider numbers with at least two digits.

Step 2: Reformulate as prefix counts

The answer is count(high) - count(low - 1) = count(13) - count(10). We will compute both via the dfs function.

Step 3: Compute a = count(low - 1) = count(10)

Set num = "10". We call dfs(0, 0, True). We are building two-digit numbers ≤ 10.

At pos = 0 (position 1, odd in 1-based, but pos % 2 == 0 so we add the digit to diff), with lim = True, the upper bound up = int(num[0]) = 1. We try digits i = 0 and i = 1.
- i = 0: recurse dfs(1, 0 + 0, lim = (True and 0 == 1) = False).
  - At pos = 1 (pos % 2 == 1, so we subtract), lim = False, up = 9. We try i = 0..9.
    - Only i = 0 keeps diff at 0 - 0 = 0. At pos = 2 (end), diff == 0 → counts 1. This represents the number 00, but as a prefix it corresponds to the value 0, which is below 11. The leading-zero numbers are an artifact; the difference subtraction at the end will cancel them out since they appear in both count(high) and count(low - 1).
    - All other i give diff != 0 → 0.
  - Subtotal: 1.
- i = 1: recurse dfs(1, 0 + 1 = 1, lim = (True and 1 == 1) = True).
  - At pos = 1, lim = True, up = int(num[1]) = 0. Only i = 0.
    - diff = 1 - 0 = 1. At end, diff != 0 → 0.
  - Subtotal: 0.
So a = count(10) = 1 (this is the leading-zero "0" being counted).

Step 4: Compute b = count(high) = count(13)

Clear the cache (num changed), set num = "13". Call dfs(0, 0, True). We build two-digit numbers ≤ 13.

At pos = 0, lim = True, up = 1. Try i = 0, 1.
- i = 0: recurse dfs(1, 0, lim = False), up = 9. Try i = 0..9.
  - i = 0 → diff = 0 → end counts 1 (the "0" artifact again).
  - others → 0.
  - Subtotal: 1.
- i = 1: recurse dfs(1, diff = 1, lim = True), up = int(num[1]) = 3. Try i = 0, 1, 2, 3.
  - i = 0 → diff = 1 - 0 = 1 → 0.
  - i = 1 → diff = 1 - 1 = 0 → end counts 1 (this is the number 11!).
  - i = 2 → diff = -1 → 0.
  - i = 3 → diff = -2 → 0.
  - Subtotal: 1.
So b = count(13) = 2 (the "0" artifact plus the genuine balanced number 11).

Step 5: Take the difference

The answer is b - a = 2 - 1 = 1.

The leading-zero artifact (the count for value 0) cancels out cleanly because it is present in both prefix counts. The final result 1 correctly identifies 11 as the only balanced integer in [10, 13].

Solution Implementation

1from functools import cache
2
3
4class Solution:
5    def countBalanced(self, low: int, high: int) -> int:
6        # Count balanced numbers in the inclusive range [1, limit].
7        # A number is "balanced" when the sum of digits at even indices
8        # equals the sum of digits at odd indices.
9        def count_up_to(limit: int) -> int:
10            digits = str(limit)
11            n = len(digits)
12
13            @cache
14            def dfs(pos: int, diff: int, bounded: bool) -> int:
15                # pos:     current digit index being filled
16                # diff:    (sum of even-index digits) - (sum of odd-index digits)
17                # bounded: True if the prefix so far matches the upper limit exactly,
18                #          which constrains the current digit's max value
19                if pos >= n:
20                    # A fully-built number is balanced only when the difference is zero
21                    return 1 if diff == 0 else 0
22
23                total = 0
24                # If bounded, the current digit cannot exceed the limit's digit
25                upper = int(digits[pos]) if bounded else 9
26                for d in range(upper + 1):
27                    # Even positions add to diff, odd positions subtract
28                    delta = d if pos % 2 == 0 else -d
29                    total += dfs(
30                        pos + 1,
31                        diff + delta,
32                        bounded and d == upper,
33                    )
34                return total
35
36            result = dfs(0, 0, True)
37            dfs.cache_clear()  # clear cache since it is tied to this `limit`
38            return result
39
40        # The smallest possible balanced number is 11 (1 == 1).
41        # Any value below 11 contributes nothing.
42        if high < 11:
43            return 0
44        low = max(low, 11)
45
46        # Inclusive range count via prefix subtraction: count(high) - count(low - 1)
47        return count_up_to(high) - count_up_to(low - 1)
48

1class Solution {
2    // Digits of the current upper bound being processed
3    private char[] digits;
4    // Memoization table: memo[position][difference + OFFSET]
5    private Long[][] memo;
6    // Offset to map negative differences into a non-negative array index.
7    // Max possible difference magnitude: 9 digits * 9 (at most) on one side,
8    // so a value of 90 safely covers the range.
9    private final int OFFSET = 90;
10
11    /**
12     * Counts "balanced" numbers in the inclusive range [low, high].
13     * A number is balanced when the sum of digits located at even indices
14     * equals the sum of digits located at odd indices.
15     *
16     * @param low  lower bound (inclusive)
17     * @param high upper bound (inclusive)
18     * @return count of balanced numbers within the range
19     */
20    public long countBalanced(long low, long high) {
21        // The smallest balanced number has at least 2 digits (e.g. 11),
22        // so anything below 11 contributes nothing.
23        if (high < 11) {
24            return 0;
25        }
26        // Clamp the lower bound to the minimum meaningful value.
27        low = Math.max(low, 11);
28
29        // Count balanced numbers in [0, low - 1].
30        digits = String.valueOf(low - 1).toCharArray();
31        memo = new Long[digits.length][(OFFSET << 1) | 1];
32        long countBelowLow = dfs(0, 0, true);
33
34        // Count balanced numbers in [0, high].
35        digits = String.valueOf(high).toCharArray();
36        memo = new Long[digits.length][(OFFSET << 1) | 1];
37        long countUpToHigh = dfs(0, 0, true);
38
39        // Numbers in [low, high] = f(high) - f(low - 1).
40        return countUpToHigh - countBelowLow;
41    }
42
43    /**
44     * Digit DP search.
45     *
46     * @param pos     current digit position being filled (from most significant)
47     * @param diff    running difference: (sum of even-index digits) - (sum of odd-index digits)
48     * @param limited whether the prefix so far matches the upper bound exactly,
49     *                which constrains the maximum digit usable at this position
50     * @return number of valid (balanced) completions from this state
51     */
52    private long dfs(int pos, int diff, boolean limited) {
53        // Base case: all positions filled; balanced iff the difference is zero.
54        if (pos >= digits.length) {
55            return diff == 0 ? 1 : 0;
56        }
57
58        // Reuse memoized result only when not bound by the upper limit,
59        // because limited states are path-specific and not reusable.
60        if (!limited && memo[pos][diff + OFFSET] != null) {
61            return memo[pos][diff + OFFSET];
62        }
63
64        // Upper bound for the digit at this position.
65        int upper = limited ? digits[pos] - '0' : 9;
66        long result = 0;
67
68        // Try every allowable digit at the current position.
69        for (int d = 0; d <= upper; ++d) {
70            // Even positions add to the difference, odd positions subtract.
71            int delta = (pos % 2 == 0) ? d : -d;
72            result += dfs(pos + 1, diff + delta, limited && d == upper);
73        }
74
75        // Cache only unconstrained states.
76        if (!limited) {
77            memo[pos][diff + OFFSET] = result;
78        }
79        return result;
80    }
81}
82

1class Solution {
2public:
3    string numStr;                  // String representation of the current upper bound
4    long long memo[20][181];        // Memoization table: memo[position][difference + offset]
5    static constexpr int offset = 90;  // Offset to keep the difference index non-negative
6
7    // Digit DP function to count numbers whose alternating digit sum difference is zero.
8    // pos      : current digit position being processed
9    // diff     : running difference (sum of even-index digits - sum of odd-index digits)
10    // isLimited: whether the current prefix is still bounded by numStr (tight constraint)
11    long long dfs(int pos, int diff, bool isLimited) {
12        // Base case: all digits processed; valid only if the difference is balanced (zero)
13        if (pos >= static_cast<int>(numStr.size())) {
14            return diff == 0 ? 1LL : 0LL;
15        }
16
17        // Use memoized result when not under the tight constraint
18        if (!isLimited && memo[pos][diff + offset] != -1) {
19            return memo[pos][diff + offset];
20        }
21
22        // Determine the maximum digit allowed at this position
23        int upperBound = isLimited ? numStr[pos] - '0' : 9;
24        long long result = 0;
25
26        // Try every possible digit at the current position
27        for (int digit = 0; digit <= upperBound; ++digit) {
28            // Even positions add, odd positions subtract
29            int sign = (pos % 2 == 0) ? 1 : -1;
30            result += dfs(pos + 1, diff + digit * sign, isLimited && digit == upperBound);
31        }
32
33        // Cache the result when the tight constraint is not active
34        if (!isLimited) {
35            memo[pos][diff + offset] = result;
36        }
37
38        return result;
39    }
40
41    // Count balanced numbers in the inclusive range [low, high].
42    // A balanced number has its even-indexed and odd-indexed digit sums equal.
43    long long countBalanced(long long low, long long high) {
44        // The smallest valid balanced number considered here is 11
45        if (high < 11) {
46            return 0;
47        }
48        low = max(low, 11LL);
49
50        // Count valid numbers in [0, low - 1]
51        numStr = to_string(low - 1);
52        memset(memo, -1, sizeof(memo));
53        long long countBelowLow = dfs(0, 0, true);
54
55        // Count valid numbers in [0, high]
56        numStr = to_string(high);
57        memset(memo, -1, sizeof(memo));
58        long long countUpToHigh = dfs(0, 0, true);
59
60        // Numbers in [low, high] = count(high) - count(low - 1)
61        return countUpToHigh - countBelowLow;
62    }
63};
64

1// Offset used to map a possibly-negative difference into a valid array index.
2const BASE = 90;
3
4// The current upper-bound number (as a string) being processed by the DFS.
5let numStr: string;
6// Memoization table: memo[position][difference + BASE] stores cached results.
7let memo: number[][];
8
9/**
10 * Digit DP routine that counts the numbers from 0 up to `numStr`
11 * whose even-position digit sum equals their odd-position digit sum.
12 *
13 * @param position The current digit index being filled.
14 * @param difference Running value of (even-position digit sum - odd-position digit sum).
15 * @param limited Whether the current prefix is still tight against `numStr`.
16 * @returns The count of valid (balanced) numbers from this state.
17 */
18function dfs(position: number, difference: number, limited: boolean): number {
19    // Base case: all positions filled; valid only if even/odd sums are equal.
20    if (position >= numStr.length) {
21        return difference === 0 ? 1 : 0;
22    }
23
24    // Reuse a cached result only when not bounded by the upper limit.
25    if (!limited && memo[position][difference + BASE] !== -1) {
26        return memo[position][difference + BASE];
27    }
28
29    // Maximum digit allowed at this position (bounded if still limited).
30    const upperDigit = limited ? numStr.charCodeAt(position) - 48 : 9;
31    let result = 0;
32
33    // Try every permissible digit at the current position.
34    for (let digit = 0; digit <= upperDigit; ++digit) {
35        // Even positions add to the difference, odd positions subtract.
36        const delta = position % 2 === 0 ? digit : -digit;
37        result += dfs(position + 1, difference + delta, limited && digit === upperDigit);
38    }
39
40    // Cache the unconstrained result for future reuse.
41    if (!limited) {
42        memo[position][difference + BASE] = result;
43    }
44
45    return result;
46}
47
48/**
49 * Counts balanced numbers in the inclusive range [low, high].
50 * A number is "balanced" when the sum of its even-indexed digits
51 * equals the sum of its odd-indexed digits.
52 *
53 * @param low  Lower bound of the range.
54 * @param high Upper bound of the range.
55 * @returns The count of balanced numbers within [low, high].
56 */
57function countBalanced(low: number, high: number): number {
58    // Balanced numbers require at least two digits; anything below 11 is impossible.
59    if (high < 11) {
60        return 0;
61    }
62    if (low < 11) {
63        low = 11;
64    }
65
66    // Count balanced numbers in [0, low - 1].
67    numStr = String(low - 1);
68    memo = Array.from(
69        { length: numStr.length },
70        () => Array<number>((BASE << 1) | 1).fill(-1),
71    );
72    const lowerCount = dfs(0, 0, true);
73
74    // Count balanced numbers in [0, high].
75    numStr = String(high);
76    memo = Array.from(
77        { length: numStr.length },
78        () => Array<number>((BASE << 1) | 1).fill(-1),
79    );
80    const upperCount = dfs(0, 0, true);
81
82    // Range result via inclusion-exclusion: count(high) - count(low - 1).
83    return upperCount - lowerCount;
84}
85

Time and Space Complexity

Time complexity: O(log² M × D²), where M is the value of high and D = 10. The recursive function dfs is memoized over the states pos and diff (the parameter lim only contributes a constant factor since it is True along just one path). The pos parameter ranges over O(log M) values (the number of digits), and the diff parameter ranges over O(log M × D) values (the cumulative difference of digits weighted by position can vary across roughly 9 × log M magnitudes). Thus the number of distinct states is O(log² M × D). For each state, the inner loop iterates up to D times, yielding a total time complexity of O(log² M × D²).
Space complexity: O(log² M × D), where M is the value of high and D = 10. The space is dominated by the memoization cache, which stores one entry per distinct state (pos, diff). With O(log M) possible values for pos and O(log M × D) possible values for diff, the total number of cached states is O(log² M × D). The recursion depth is O(log M), which is dominated by the cache size.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Inconsistent Position Parity Across Numbers of Different Lengths

The most subtle and dangerous pitfall in this solution lies in how "even" and "odd" positions are determined. The problem defines positions from the left, starting at 1. However, the code uses pos % 2 == 0 based on the internal index pos (which starts at 0 for the leftmost digit).

This creates a fundamental inconsistency: for two numbers of different lengths, the same actual "position from the left, starting at 1" maps to a different parity check. But more importantly, the @cache is tied to a single limit, and the parity is always measured relative to the leftmost digit of that specific number's length.

Consider the prefix-subtraction technique: count_up_to(high) - count_up_to(low - 1). When high and low - 1 have different numbers of digits, the leftmost digit of each is at index pos = 0, but their "balance" is computed relative to their own length. Since the definition of balanced depends on the alignment of positions, the difference is only valid if both counts use the same positional alignment for every individual number.

Fortunately, because each number's balance is self-contained (the parity is decided per-number by its own leftmost digit at pos = 0), this actually works out — but only because we count each number independently. The danger arises if someone "optimizes" by padding numbers to a common length with leading zeros:

# WRONG: padding shifts the parity of every digit!
digits = str(limit).zfill(MAX_LEN)

Padding with leading zeros shifts the leftmost real digit to a higher pos, flipping its parity. A number like 11 (positions 1,2) padded to 0011 would have its real digits at positions 3,4, completely changing which sum they contribute to.

Solution: Never pad numbers to a common length. Compute each number's balance based on its own actual length, with the leftmost digit always at pos = 0. The current code does this correctly by using digits = str(limit) without padding.

Pitfall 2: Forgetting to Clear the Cache Between Different Limits

The @cache memoizes on (pos, diff, bounded). The meaning of these states is tied to the specific digits string of the current limit. The bounded=True branch reads int(digits[pos]), so cached values computed for high are invalid when reused for low - 1.

In this code, dfs is redefined inside count_up_to, so each call gets a fresh closure and fresh cache — the dfs.cache_clear() is actually redundant here but harmless. However, a common mistake is to define dfs once at the class/method level and share it across both limits:

# WRONG: shared cache across different limits corrupts results
@cache
def dfs(pos, diff, bounded): ...
a = dfs(0, 0, True)   # uses digits of high
# digits changes to low-1
b = dfs(0, 0, True)   # returns STALE cached values from high!

Solution: Either redefine dfs per limit (as done here) so each gets its own cache, or explicitly call dfs.cache_clear() before processing a new limit.

Pitfall 3: Caching the `bounded=True` States Pollutes the Cache

A more performance-oriented pitfall: states where bounded=True are visited at most once each (they lie on the single path matching the limit exactly). Caching them wastes memory and, more critically, mixes limit-specific states with limit-independent states.

The bounded=True states depend on digits, while bounded=False states are fully general (independent of the limit). If the cache is reused across limits, the bounded=False entries are reusable but the bounded=True entries are not.

Solution: A cleaner design excludes bounded from caching:

@cache
def dfs_free(pos, diff):  # only the bounded=False case is cached
    if pos >= n:
        return 1 if diff == 0 else 0
    total = 0
    for d in range(10):
        delta = d if pos % 2 == 0 else -d
        total += dfs_free(pos + 1, diff + delta)
    return total

def dfs(pos, diff, bounded):
    if not bounded:
        return dfs_free(pos, diff)
    if pos >= n:
        return 1 if diff == 0 else 0
    total = 0
    upper = int(digits[pos])
    for d in range(upper + 1):
        delta = d if pos % 2 == 0 else -d
        total += dfs(pos + 1, diff + delta, d == upper)
    return total

This separates the truly reusable (limit-independent) cache from the one-shot bounded path.

Pitfall 4: Off-by-One in the Lower Boundary

A classic interval-counting mistake is computing count_up_to(high) - count_up_to(low), which excludes low itself when low is balanced. The correct subtraction must use low - 1 to keep the range inclusive:

return count_up_to(high) - count_up_to(low - 1)  # correct, inclusive of low

Solution: Always remember the identity count[low, high] = count[1, high] - count[1, low - 1] and verify with a small example (e.g., low = high = 11 should return 1, not 0).

Pitfall 5: Negative `diff` Values and Hashability

Since odd positions subtract and even positions add, diff can be negative. This is fine for Python's @cache (negative ints are valid, hashable keys), but if you reimplement the memoization with a fixed-size array indexed by diff, you must offset the index (e.g., diff + MAX_SUM) to avoid negative indices and out-of-bounds errors.

Solution: When using array-based memoization, add an offset:

OFFSET = 9 * len(digits)  # max possible |diff|
memo = [[-1] * (2 * OFFSET + 1) for _ in range(n + 1)]
# access via memo[pos][diff + OFFSET]

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering