Sum of Digit Differences of All Pairs
MedPrompt
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 in the two integers.
Return the sum of the digit differences between all pairs of integers in nums.
Example 1:
Input: nums = [13,23,12]
Output: 4
Explanation:
We have the following:
- The digit difference between 13 and 23 is 1.
- The digit difference between 13 and 12 is 1.
- The digit difference between 23 and 12 is 2.
So the total sum of digit differences between all pairs of integers is 1 + 1 + 2 = 4.
Example 2:
Input: nums = [10,10,10,10]
Output: 0
Explanation:
All the integers in the array are the same. So the total sum of digit differences between all pairs of integers will be 0.
Constraints:
2 <= nums.length <= 1051 <= nums[i] < 109- All integers in
numshave the same number of digits.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. It iterates through every unique pair of numbers in the input array, calculates the digit difference for each pair by comparing their digits one by one, and sums up these differences.
Algorithm
- Initialize a variable
totalDifferenceto 0. - Use two nested loops to iterate through all unique pairs of indices
(i, j)wherei < j. - For each pair
(nums[i], nums[j]):- Create temporary copies of the numbers, say
num1andnum2. - Start a loop that continues as long as the numbers are positive (since all have the same length, checking one is sufficient).
- In each iteration of this inner loop, extract the last digit of
num1andnum2using the modulo operator (% 10). - If the digits are different, increment
totalDifference. - Update
num1andnum2by dividing them by 10 to process the next digit.
- Create temporary copies of the numbers, say
- After iterating through all pairs, return
totalDifference.
Walkthrough
The algorithm employs two nested loops to generate all unique pairs of numbers, (nums[i], nums[j]) where i < j. For each pair, an inner loop is used to compare their digits at each position. To extract digits, the numbers are repeatedly divided by 10, and the remainder (% 10) gives the last digit. This process continues from the least significant digit to the most significant. A global counter for the total difference is maintained and incremented for each position where the digits of the pair do not match. The final sum is returned after all pairs have been processed.
class Solution { public long sumDigitDifferences(int[] nums) { long totalDifference = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int num1 = nums[i]; int num2 = nums[j]; // Since all numbers have the same number of digits, // we can iterate while one of them is > 0. while (num1 > 0) { if (num1 % 10 != num2 % 10) { totalDifference++; } num1 /= 10; num2 /= 10; } } } return totalDifference; }}Complexity
Time
O(N² * D), where N is the number of elements in `nums` and D is the number of digits in each number. There are O(N²) pairs, and for each pair, we perform O(D) work to compare all their digits. Given N can be up to 10⁵, this approach is too slow.
Space
O(1) extra space. We only use a few variables to store loop counters and the running sum.
Trade-offs
Pros
Simple to understand and straightforward to implement.
Cons
Highly inefficient due to its quadratic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the problem constraints.
This optimized approach reframes the problem to achieve a much better time complexity. Instead of iterating through pairs of numbers, it iterates through each digit position (units, tens, hundreds, etc.) and calculates the total contribution to the sum from that position. The final answer is the sum of these contributions.
Algorithm
- The total sum of differences can be seen as the sum of contributions from each digit position.
- Initialize
totalDifference = 0L. - Determine the number of digits,
D, from any number in the array (e.g.,String.valueOf(nums[0]).length()). - Loop through each digit position
pfrom 0 toD-1(from units place upwards).- For each position
p:- Initialize a frequency array
counts = new int[10]to store the counts of digits 0-9. - Iterate through each number
numin thenumsarray. - Extract the digit at position
pusing(num / divisor) % 10, wheredivisoris 10ᵖ. - Increment the frequency of the extracted digit in the
countsarray. - After counting all digits for the current position, calculate the number of pairs with different digits.
- For each digit
d(0-9), if its count isc, it formsc * (n - c)pairs with numbers that have a different digit at this position. - Sum
c * (n - c)for alld. This sum counts each differing pair twice, so divide it by 2 to get the contribution for the current position. - Add this contribution to
totalDifference.
- Initialize a frequency array
- For each position
- After iterating through all digit positions, return
totalDifference.
Walkthrough
The core idea is that the total sum of digit differences is the sum of differences calculated independently at each digit position. The algorithm iterates from the least significant digit to the most significant. For each position, it first counts the frequency of each digit (0-9) across all numbers in the input array. This is done by iterating through nums and using modular arithmetic to isolate the digit at the current position.
Once the frequencies are known for a position, we can calculate how many pairs have different digits at this position. If c numbers have a digit d, and there are n numbers in total, then these c numbers can be paired with n - c numbers that have a different digit. This contributes c * (n - c) to a running sum. By summing this value over all possible digits (0-9), we get the total number of differing pairs, but with each pair counted twice. Therefore, the contribution for the current position is (sum of c * (n - c)) / 2.
This process is repeated for all digit positions, and their contributions are summed up to get the final result.
class Solution { public long sumDigitDifferences(int[] nums) { int n = nums.length; if (n <= 1) { return 0; } long totalDifference = 0; // All numbers have the same number of digits. int numDigits = String.valueOf(nums[0]).length(); long divisor = 1; for (int p = 0; p < numDigits; p++) { int[] counts = new int[10]; for (int num : nums) { int digit = (int) ((num / divisor) % 10); counts[digit]++; } long positionDifference = 0; for (int count : counts) { positionDifference += (long)count * (n - count); } totalDifference += positionDifference / 2; if (p < numDigits - 1) { divisor *= 10; } } return totalDifference; }}Complexity
Time
O(N * D), where N is the number of elements in `nums` and D is the number of digits. We have an outer loop that runs D times, and an inner loop that runs N times. This is a significant improvement over the brute-force approach.
Space
O(1) extra space. We only need a constant-size array (`counts`) of size 10 for frequencies and a few variables for calculations, regardless of the input size.
Trade-offs
Pros
Highly efficient with a linear time complexity relative to the total number of digits in the input.
Easily handles the maximum constraints of the problem.
Cons
The logic is less direct than the brute-force approach and requires a change in perspective to understand.
Solutions
Solution
class Solution {public long sumDigitDifferences(int[] nums) { int n = nums.length; int m = (int)Math.floor(Math.log10(nums[0])) + 1; int[] cnt = new int[10]; long ans = 0; for (int k = 0; k < m; ++k) { Arrays.fill(cnt, 0); for (int i = 0; i < n; ++i) { ++cnt[nums[i] % 10]; nums[i] /= 10; } for (int i = 0; i < 10; ++i) { ans += 1L * cnt[i] * (n - cnt[i]); } } return ans / 2; }}class Solution {public: long long sumDigitDifferences(vector<int> &nums) { int n = nums.size(); int m = floor(log10(nums[0])) + 1; int cnt[10]; long long ans = 0; for (int k = 0; k < m; ++k) { memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < n; ++i) { ++cnt[nums[i] % 10]; nums[i] /= 10; } for (int i = 0; i < 10; ++i) { ans += 1LL * (cnt[i] * (n - cnt[i])); } } return ans / 2; }};class Solution: def sumDigitDifferences(self, nums: List[int]) -> int: n = len(nums) m = int(log10(nums[0])) + 1 ans = 0 for _ in range(m): cnt = Counter() for i, x in enumerate(nums): nums[i], y = divmod(x, 10) cnt[y] += 1 ans += sum(v * (n - v) for v in cnt . values()) // 2 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.