Number of balanced integers in a range

Dynamic Programming

34.8% acceptance

Feb 25, 2026

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). Return an integer representing the number of balanced integers in the range [low, high] (both inclusive).

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_balanced(low: i64, high: i64) -> i64 {
    Self::f(high) - Self::f(low - 1)
  }

  fn f(n: i64) -> i64 {
    if n <= 10 { return 0; } // no 1-digit or single-digit balanced numbers; 2-digit start at 11
    let s: Vec<i32> = n.to_string().bytes().map(|b| (b - b'0') as i32).collect();
    let len = s.len();
    let mut result = 0i64;

    // Numbers with exactly d digits where d >= 2
    for d in 2..len {
      result += Self::count_balanced_d(d, &vec![9i32; d], false);
    }
    if len >= 2 {
      result += Self::count_balanced_d(len, &s, true);
    }
    result
  }

  // Count d-digit balanced integers <= limit (if tight)
  // Balanced: sum of odd-position digits == sum of even-position digits
  // Positions: leftmost = position 1 (odd), then 2 (even), etc.
  // diff = sum_odd - sum_even; balanced iff diff == 0 and d >= 2
  fn count_balanced_d(d: usize, limit: &[i32], tight_init: bool) -> i64 {
    use std::collections::HashMap;
    // State: (tight, diff) where diff = sum_odd - sum_even so far (can be negative)
    // diff ranges: at most d*9 in absolute value, so -d*9..=d*9
    let mut dp: HashMap<(bool, i32), i64> = HashMap::new();
    dp.insert((tight_init, 0), 1);

    for pos in 0..d {
      let mut new_dp: HashMap<(bool, i32), i64> = HashMap::new();
      let lo = if pos == 0 { 1 } else { 0 };
      // position in number is 1-indexed: pos 0 -> position 1 (odd), pos 1 -> position 2 (even)
      let sign: i32 = if pos % 2 == 0 { 1 } else { -1 }; // pos 0 is position 1 (odd) -> +1
      for (&(t, diff), &cnt) in &dp {
        let hi = if t { limit[pos] } else { 9 };
        for digit in lo..=hi {
          let new_tight = t && digit == limit[pos];
          let new_diff = diff + sign * digit;
          *new_dp.entry((new_tight, new_diff)).or_insert(0) += cnt;
        }
      }
      dp = new_dp;
    }
    dp.iter().filter(|&(&(_, diff), _)| diff == 0).map(|(_, &c)| c).sum()
  }
}