Count no zero pairs that sum to n

Math Dynamic Programming

14.3% acceptance

Feb 24, 2026

A no-zero integer is a positive integer that does not contain the digit 0 in its decimal representation. Given an integer n, count the number of pairs (a, b) where: a and b are no-zero integers. a + b = n Return an integer denoting the number of such pairs.

Solution

Rust

Time O(n * m)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_no_zero_pairs(n: i64) -> i64 {
    // Build digit array (LSB first)
    let mut digits = Vec::new();
    let mut tmp = n;
    while tmp > 0 {
      digits.push((tmp % 10) as usize);
      tmp /= 10;
    }
    let l = digits.len();

    // For each (k, m): count pairs where a has exactly k digits and b has exactly m digits
    // a_i in [1,9] for i < k, else 0; b_i in [1,9] for i < m, else 0
    // a + b = n, carry propagates from LSB
    // dp[pos][carry] = number of valid completions
    let mut total = 0i64;

    for k in 1..=l {
      for m in 1..=l {
        // dp over positions 0..l with carry in {0, 1}
        let mut dp = vec![[0i64; 2]; l + 1];
        dp[l][0] = 1;

        for pos in (0..l).rev() {
          let nd = digits[pos];
          for carry in 0..2usize {
            let mut cnt = 0i64;
            let a_lo = if pos < k { 1 } else { 0 };
            let a_hi = if pos < k { 9 } else { 0 };
            let b_lo = if pos < m { 1 } else { 0 };
            let b_hi = if pos < m { 9 } else { 0 };
            for ai in a_lo..=a_hi {
              for bi in b_lo..=b_hi {
                let s = ai + bi + carry;
                if s % 10 == nd && s / 10 <= 1 {
                  cnt += dp[pos + 1][s / 10];
                }
              }
            }
            dp[pos][carry] = cnt;
          }
        }

        total += dp[0][0];
      }
    }

    total
  }
}