3153. Sum of Digit Differences of All Pairs

MediumArrayHash TableMathCounting

Problem Description

You are given an array nums consisting of positive integers where all integers have the same number of digits. The task is to calculate the sum of the digit differences between all pairs of integers in nums.

The digit difference between two integers refers to the count of digits that differ in the same position. Return the sum of the digit differences between all pairs of integers in nums.

Intuition

The problem can be approached by leveraging counting techniques. Given that all numbers have the same number of digits, we can cycle through each digit position and evaluate differences. For each position, count how often each digit appears using a counter.

For example, if a digit occurs v times across all numbers at a certain position, then it will be different from (n - v) numbers at that same digit position, where n is the total number of integers. So, the contribution to the digit difference from this position is v * (n - v).

By doing this for each digit position in each number, you effectively count all pairwise digit differences. Since you've counted each pair twice, once for each order, you'll need to divide this sum by 2 to get the correct result.

This insight helps reduce the problem to simple counting and arithmetic, using a loop for each digit position and a counter for efficiency.

Learn more about Math patterns.

Solution Approach

The solution utilizes a counting approach to efficiently calculate the sum of digit differences between all pairs of integers in the nums array. Here's a breakdown of the implementation:

Identify Number of Digits: Calculate the number of digits m in each number. Since all integers have the same number of digits, this can be computed using:
```
m = int(log10(nums[0])) + 1
```
Iterate Over Each Digit Position: Loop over each digit position, starting from the least significant digit.
Counting Occurrences: For each digit position:
- Initialize a counter cnt to keep track of how many times each digit appears at this position among all numbers.
- For each number, extract the current digit using division and modulo:
```
nums[i], y = divmod(x, 10)
```
- Update the counter with the current digit:
```
cnt[y] += 1
```
Calculate Digit Differences: For each digit position, calculate the contribution to the digit differences using the formula:
```
sum(v * (n - v) for v in cnt.values()) // 2
```
Here, v represents the frequency of a particular digit, and n is the total number of integers. Each pair contributes to the digit difference based on how often a digit differs between numbers.
Accumulate the Results: Sum the contributions for all digit positions to get the final result.

This approach effectively breaks down the large problem into smaller, manageable tasks of counting occurrences and calculating contributions, leading to an efficient solution.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the array nums = [123, 456, 789].

Number of Digits: Each number in nums has the same number of digits. Here, each number is a 3-digit integer.
Iterate Over Each Digit Position: We will evaluate each digit position one by one.
- First Position (Least Significant Digit):
  - For 123, the least significant digit is 3.
  - For 456, the least significant digit is 6.
  - For 789, the least significant digit is 9.
  Using a counter, we find:
  - 3 appears once.
  - 6 appears once.
  - 9 appears once.
  The contribution to the digit differences from this position is calculated as:
  - There are 3 numbers in total. For 3, the contribution is 1 * (3 - 1) = 2.
  - Similarly, for 6, the contribution is 2, and for 9, it is 2.
  Sum for this position = 2 + 2 + 2 = 6.
- Second Position:
  - For 123, the second digit is 2.
  - For 456, the second digit is 5.
  - For 789, the second digit is 8.
  Using a counter, we again determine:
  - 2, 5, and 8 each appear once.
  Contributions:
  - Each digit contributes 2, leading to a total of 6 for this position.
- Third Position (Most Significant Digit):
  - For 123, the third digit is 1.
  - For 456, the third digit is 4.
  - For 789, the third digit is 7.
  A similar counting shows:
  - 1, 4, and 7 each appear once.
  Contributions:
  - Again, each digit contributes 2, totaling 6 for this position.
Accumulation: Adding up all contributions from each digit position, the total sum of digit differences between all pairs in the array is 6 + 6 + 6 = 18.

This process efficiently captures the essence of digit differences by iterating through each digit position and calculating their contribution to the total by counting occurrences. The final result shows the sum of how many digits differ across all possible pairs in the input array nums.

Solution Implementation

1from typing import List
2from collections import Counter
3from math import log10
4
5class Solution:
6    def sumDigitDifferences(self, nums: List[int]) -> int:
7        # Number of elements in the list
8        n = len(nums)
9      
10        # Determine the number of digits in the first number
11        m = int(log10(nums[0])) + 1
12      
13        # Initialize answer to store the sum of differences
14        ans = 0
15      
16        # Loop over each digit position (from least significant to most significant)
17        for _ in range(m):
18            # Initialize Counter for counting occurrences of each digit at the current position
19            cnt = Counter()
20          
21            # Iterate over numbers
22            for i, x in enumerate(nums):
23                # Split each number into a smaller number (remaining digits) and the current digit
24                nums[i], y = divmod(x, 10)
25              
26                # Count the occurrences of each digit
27                cnt[y] += 1
28          
29            # Calculate the sum of digit differences
30            # For each digit's count, contribute to the result based on combinations
31            ans += sum(v * (n - v) for v in cnt.values()) // 2
32      
33        # Return the total sum of digit differences
34        return ans
35

1import java.util.Arrays;
2
3class Solution {
4    public long sumDigitDifferences(int[] nums) {
5        int n = nums.length; // Get the number of elements in the array
6        int m = (int) Math.floor(Math.log10(nums[0])) + 1; // Determine the number of digits in the first number
7        int[] count = new int[10]; // Array to count digit frequencies from 0 to 9
8        long totalDifference = 0; // Variable to accumulate the total sum of digit differences
9
10        // Iterate over each digit place (units, tens, hundreds, etc.)
11        for (int k = 0; k < m; ++k) {
12            Arrays.fill(count, 0); // Reset digit frequency count for each place
13
14            // Count the occurrence of each digit at the k-th position
15            for (int i = 0; i < n; ++i) {
16                ++count[nums[i] % 10]; // Increment count for the last digit
17                nums[i] /= 10; // Remove the last digit by dividing by 10
18            }
19
20            // Calculate differences based on the counting result
21            for (int i = 0; i < 10; ++i) {
22                totalDifference += 1L * count[i] * (n - count[i]); // Update total by the product of pairs
23            }
24        }
25        return totalDifference / 2; // Divide by 2 to account for double-counting
26    }
27}
28

1#include <vector>
2#include <cmath> // For log10
3#include <cstring> // For memset
4
5class Solution {
6public:
7    long long sumDigitDifferences(std::vector<int>& nums) {
8        int n = nums.size(); // Number of elements in the input vector
9        int m = static_cast<int>(std::floor(std::log10(nums[0]))) + 1; // Determine the number of digits in the first number
10        int cnt[10]; // Array to count occurrences of each digit 0-9
11        long long ans = 0; // Resultant sum of differences of digits
12      
13        // Iterate over each possible digit position
14        for (int k = 0; k < m; ++k) {
15            std::memset(cnt, 0, sizeof(cnt)); // Reset digit count to zero
16            // Count digits in the current position for all numbers
17            for (int i = 0; i < n; ++i) {
18                ++cnt[nums[i] % 10]; // Increment count for the digit at the current position
19                nums[i] /= 10; // Remove last digit to shift to the next position for the next iteration
20            }
21            // Calculate the contribution of the current digit position to the answer
22            for (int i = 0; i < 10; ++i) {
23                ans += 1LL * cnt[i] * (n - cnt[i]); // Add the product of the number of pairs that have different digits
24            }
25        }
26        return ans / 2; // Since each difference is counted twice, divide by 2 for the final result
27    }
28};
29

1/**
2 * Function to calculate the sum of digit differences for an array of numbers.
3 * @param nums - Array of non-negative numbers.
4 * @returns The sum of digit differences.
5 */
6function sumDigitDifferences(nums: number[]): number {
7    const n = nums.length; // Number of elements in nums.
8    const m = Math.floor(Math.log10(nums[0])) + 1; // Number of digits in the first number.
9    let ans: bigint = BigInt(0); // Initialize the result as a BigInt to handle large values.
10
11    // Iterate over each digit position.
12    for (let k = 0; k < m; ++k) {
13        const cnt: number[] = Array(10).fill(0); // Array to count occurrences of each digit (0-9).
14
15        // Count the occurrences of each digit at the current position.
16        for (let i = 0; i < n; ++i) {
17            ++cnt[nums[i] % 10]; // Increment the count for the current digit.
18            nums[i] = Math.floor(nums[i] / 10); // Remove the last digit.
19        }
20
21        // Calculate the sum of differences for the current digit position.
22        for (let i = 0; i < 10; ++i) {
23            ans += BigInt(cnt[i]) * BigInt(n - cnt[i]); // Sum the contribution of each digit.
24        }
25    }
26
27    // Each difference is counted twice, so divide the answer by 2.
28    ans /= BigInt(2);
29
30    // Convert the final BigInt result back to a number and return.
31    return Number(ans);
32}
33

Time and Space Complexity

The time complexity of the code is O(n * m), where n is the length of the nums array, and m is the number of digits in the maximum number in nums. This is because the outer loop runs m times, and for each iteration, the inner loop processes all n elements in nums.

The space complexity is O(C), where C is a constant representing the range of possible digit values, which is 10. This is due to maintaining a counter dictionary to store the count of each digit encountered, which can contain at most 10 different keys since digits range from 0 to 9.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know