Number of beautiful integers in the range

Math Dynamic Programming

21.6% acceptance

Feb 25, 2026

397

You are given positive integers low, high, and k. A number is beautiful if it meets both of the following conditions: The count of even digits in the number is equal to the count of odd digits. The number is divisible by k. Return the number of beautiful integers in the range [low, high].

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_beautiful_integers(low: i32, high: i32, k: i32) -> i32 {
    fn digits_of(n: i32) -> Vec<i32> {
      let mut v = vec![];
      let mut x = n;
      while x > 0 { v.push(x % 10); x /= 10; }
      v.reverse();
      v
    }

    fn count_upto(n: i32, k: usize) -> i32 {
      if n <= 0 { return 0; }
      let digits = digits_of(n);
      let len = digits.len();
      let max_diff = 2 * len + 1;
      let mut memo = vec![vec![vec![-1i32; max_diff]; k]; len];

      fn dp(
        digits: &[i32], pos: usize, modulo: usize, diff: i32,
        tight: bool, leading: bool, k: usize,
        memo: &mut Vec<Vec<Vec<i32>>>,
      ) -> i32 {
        if pos == digits.len() {
          if leading { return 0; }
          return if modulo == 0 && diff == 0 { 1 } else { 0 };
        }
        let d_idx = (diff + digits.len() as i32) as usize;
        if !tight && !leading && memo[pos][modulo][d_idx] != -1 {
          return memo[pos][modulo][d_idx];
        }
        let limit = if tight { digits[pos] as usize } else { 9 };
        let mut result = 0i32;
        for d in 0..=limit {
          let is_tight = tight && d == limit;
          if leading && d == 0 {
            result += dp(digits, pos + 1, 0, 0, is_tight, true, k, memo);
          } else {
            let new_diff = diff + if d % 2 == 0 { 1 } else { -1 };
            result += dp(digits, pos + 1, (modulo * 10 + d) % k, new_diff, is_tight, false, k, memo);
          }
        }
        if !tight && !leading { memo[pos][modulo][d_idx] = result; }
        result
      }

      dp(&digits, 0, 0, 0, true, true, k, &mut memo)
    }

    count_upto(high, k as usize) - count_upto(low - 1, k as usize)
  }
}