We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Digit Differences of All Pairs

Number: 3416

Difficulty: Medium

Paid? No

Companies: Turing, Google

Problem Description

Given an array nums of positive integers—all having the same number of digits—compute the sum of the digit differences across all unique pairs. The digit difference between two numbers is defined as the number of positions at which the corresponding digits are different.

Key Insights

  • Each number has the same number of digits so we can examine each digit position independently.
  • For any position, count the frequency of each digit across all numbers.
  • For each digit position, the total number of pairs with a difference is equal to all possible pairs minus the pairs that share the same digit at that position.
  • The overall answer is the sum of these counts for every digit position.

Space and Time Complexity

Time Complexity: O(n * L), where n is the length of nums and L is the number of digits in each number. Space Complexity: O(1) if we assume a constant digit range (0-9); otherwise O(10) for the frequency array per digit position.

Solution

We solve the problem by iterating through each digit position of the numbers. For a given position:

  1. Convert each number to its string representation (or use arithmetic, if preferred) and extract the digit at the current index.
  2. Use a frequency array (or hash table) of size 10 to count occurrences of each digit.
  3. Compute the number of pairs for this digit position. The total number of pairs among n numbers is n*(n-1)/2. Subtract the number of pairs that have the same digit (for each digit d, compute freq[d]*(freq[d]-1)/2).
  4. Sum the resulting counts from all digit positions to get the final answer.

This avoids directly iterating over every pair, which would be too slow given the constraints.

Code Solutions

# Python solution

class Solution:
    def differenceOfDigits(self, nums):
        # convert numbers to strings for easy digit access
        str_nums = [str(num) for num in nums]
        n = len(nums)
        total_difference = 0
        L = len(str_nums[0])
        
        # iterate over each digit position
        for pos in range(L):
            # frequency array for digits 0-9 at this position
            freq = [0] * 10
            for s in str_nums:
                digit = int(s[pos])
                freq[digit] += 1
                
            # compute total pairs for this position: pairs with different digits
            # total pairs among n numbers
            total_pairs = n * (n - 1) // 2
            # subtract the pairs with the same digit
            same_pairs = 0
            for count in freq:
                same_pairs += count * (count - 1) // 2
                
            # pairs with different digits at this position
            total_difference += total_pairs - same_pairs
            
        return total_difference

# Example usage:
# sol = Solution()
# print(sol.differenceOfDigits([13,23,12]))  # Output: 4
← Back to All Questions