4095. Number of Balanced Integers in a Range
My accepted Python solution to LeetCode problem 4095, Number of Balanced Integers in a Range, running in 5698ms.
- Difficulty: Hard
- Python
- Runtime 5698ms
- Memory 192.3MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 5698ms, memory 192.3MB, accepted 2025-12-29.
class Solution:
def countBalanced(self, low: int, high: int) -> int:
def count(n):
if n < 10:
return 0 # Need at least 2 digits
s = str(n)
length = len(s)
# Memoization: (pos, sum_diff, tight, started)
# sum_diff = sum of odd positions - sum of even positions
from functools import lru_cache
@lru_cache(maxsize=None)
def dp(pos, diff, tight, started, num_digits):
if pos == length:
if not started or num_digits < 2:
return 0
return 1 if diff == 0 else 0
limit = int(s[pos]) if tight else 9
result = 0
for d in range(0, limit + 1):
new_started = started or (d > 0)
new_tight = tight and (d == limit)
new_num_digits = num_digits + 1 if new_started else 0
if new_started:
# Position 1 is odd, position 2 is even, etc.
new_pos_in_num = new_num_digits
if new_pos_in_num % 2 == 1: # odd position
new_diff = diff + d
else: # even position
new_diff = diff - d
else:
new_diff = diff
result += dp(pos + 1, new_diff, new_tight, new_started, new_num_digits)
return result
return dp(0, 0, True, False, 0)
return count(high) - count(low - 1)