Linearity based on bucketization

Common problems require a bucketization strategy in order to speed up the solution. It is a tradeoff between space and time. The problem below would naively require an N^2 approach. In order to speed it up, here is the approach:

1. Count the number of digits from 0..9 in each position of the number. Notice that there are 5 positions available (since the max number is 10^5).

2. At this point, for each position, do a nested loop (0..9, nested with 0..9) multiplying the ones that are different, and adding them to the result (use a long cast to avoid overflow)

The first step takes N. The second is quicker: 5*10*10 = 500, or constant time. Works relatively fast. Code is down below. If you want to try some copilot, do it too, but the ones that I tried provided the wrong answer. Cheers, ACC.

Sum of Digit Differences of All Pairs - LeetCode

3153. Sum of Digit Differences of All Pairs

Medium

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 <= 105
• 1 <= nums[i] < 109
• All integers in nums have the same number of digits.

Accepted

13,922

Submissions

33,270

public long SumDigitDifferences(int[] nums)
{
    //Bucketize the count per position
    long[][] positionCount = new long[nums[0].ToString().Length][];
    for (int i = 0; i < positionCount.Length; i++) positionCount[i] = new long[10];

    foreach (int num in nums)
    {
        int position = positionCount.Length - 1;
        int n = num;
        while (position >= 0)
        {
            positionCount[position][n % 10]++;
            position--;
            n /= 10;
        }
    }

    long retVal = 0;
    foreach (long[] pCount in positionCount)
    {
        for (int i = 0; i < 10; i++)
        {
            if (pCount[i] > 0)
            {
                for (int j = i + 1; j < 10; j++)
                {
                    if (pCount[j] > 0)
                    {
                        retVal += (long)pCount[i] * pCount[j];
                    }
                }
            }
        }   
    }

    return retVal;
}