Another Casual Coder

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

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;
}