Skip to content

3153. Sum of Digit Differences of All Pairs 👍

  • Time: $O(n)$
  • Space: $O(10) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  long long sumDigitDifferences(vector<int>& nums) {
    const int n = nums.size();
    const int digitSize = std::to_string(nums[0]).size();
    long ans = 0;

    for (int i = 0, denominator = 1; i < digitSize; ++i, denominator *= 10) {
      vector<int> count(10);
      for (const int num : nums)
        ++count[num / denominator % 10];
      for (const int freq : count)
        ans += freq * (n - freq);
    }

    return ans / 2;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public long sumDigitDifferences(int[] nums) {
    final int n = nums.length;
    final int digitSize = String.valueOf(nums[0]).length();
    long ans = 0;

    for (int i = 0, denominator = 1; i < digitSize; ++i, denominator *= 10) {
      int[] count = new int[10];
      for (final int num : nums)
        ++count[num / denominator % 10];
      for (final int freq : count)
        ans += freq * (n - freq);
    }

    return ans / 2;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def sumDigitDifferences(self, nums: list[int]) -> int:
    n = len(nums)
    digitSize = len(str(nums[0]))
    ans = 0

    denominator = 1
    for _ in range(digitSize):
      count = [0] * 10
      for num in nums:
        count[num // denominator % 10] += 1
      ans += sum(freq * (n - freq) for freq in count)
      denominator *= 10

    return ans // 2