Sum of digit differences of all pairs

Array Hash Table Math Counting

43.0% acceptance

Feb 24, 2026

225

You are given an array nums consisting of positive integers where all integers have the same number of digits. The digit difference between two integers is the count of different digits that are in the same position. Return the sum of the digit differences between all pairs of integers in nums.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn sum_digit_differences(nums: Vec<i32>) -> i64 {
    let n = nums.len() as i64;
    // Find number of digits
    let num_digits = nums[0].to_string().len();
    let mut total = 0i64;
    for d in 0..num_digits {
      let div = 10i32.pow(d as u32);
      let mut cnt = [0i64; 10];
      for &x in &nums {
        cnt[((x / div) % 10) as usize] += 1;
      }
      // # pairs differing at digit d = total_pairs - # pairs agreeing
      let pairs = n * (n - 1) / 2;
      let same: i64 = cnt.iter().map(|&c| c * (c - 1) / 2).sum();
      total += pairs - same;
    }
    total
  }
}