Sum of Digit Differences of All Pairs - Practice Coding Problems

Sum of Digit Differences of All Pairs - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [13, 23, 12]

› Output: 4

💡 Note: Pair (13,23): digits differ at position 1 (3≠2) → +1. Pair (13,12): digits differ at position 1 (3≠2) → +1. Pair (23,12): digits differ at position 0 (2≠1) and position 1 (3≠2) → +2. Total: 1+1+2=4

Example 2 — All Same Digits

$ Input: nums = [10, 10, 10]

› Output: 0

💡 Note: All numbers are identical, so no digit positions differ between any pairs. Total differences = 0

Example 3 — Two Numbers

$ Input: nums = [123, 456]

› Output: 3

💡 Note: Only one pair (123,456): all three digit positions differ (1≠4, 2≠5, 3≠6) → +3. Total: 3

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] < 10¹⁰
All integers in nums have the same number of digits

Visualization

Tap to expand

Understanding the Visualization

Input

Array of numbers with same digit count: [13, 23, 12]

Process

Compare digits at same positions for all pairs

Output

Sum of all digit differences: 4

Key Takeaway

🎯 Key Insight: Instead of comparing every pair directly, count digit frequencies at each position and use math to calculate total differences efficiently

Asked in

G Google 15 M Microsoft 12

The key insight is to count digit frequencies at each position and use mathematical formulas instead of comparing every pair. The optimal approach uses frequency counting to achieve O(n×d) time complexity, where n is array length and d is number of digits. For each position, calculate different pairs as total_pairs - same_digit_pairs. Time: O(n×d), Space: O(d)

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count Optimization	O(n × d)	O(d)	Count digit frequencies at each position and calculate differences mathematically
Brute Force	O(n² × d)	O(1)	Compare every pair of numbers digit by digit

Frequency Count Optimization — Algorithm Steps

For each digit position, count frequency of each digit 0-9
For each position, calculate pairs with different digits
Sum differences across all positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

For each position, count how many of each digit

Calculate Same Pairs

Use formula: freq[i] * (freq[i]-1) / 2

Get Different Pairs

Total pairs - Same pairs = Different pairs

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    
    char temp[20];
    sprintf(temp, "%d", nums[0]);
    int numDigits = strlen(temp);
    long long totalDiff = 0;
    
    for (int pos = 0; pos < numDigits; pos++) {
        int freq[10] = {0};
        
        for (int i = 0; i < numsSize; i++) {
            sprintf(temp, "%d", nums[i]);
            int digit = temp[pos] - '0';
            freq[digit]++;
        }
        
        long long samePairs = 0;
        for (int i = 0; i < 10; i++) {
            samePairs += (long long)freq[i] * (freq[i] - 1) / 2;
        }
        
        long long totalPairs = (long long)numsSize * (numsSize - 1) / 2;
        long long diffPairs = totalPairs - samePairs;
        totalDiff += diffPairs;
    }
    
    return totalDiff;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int count = 0;
    char* ptr = line + 1;
    
    while (*ptr && *ptr != ']') {
        nums[count++] = atoi(ptr);
        while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        if (*ptr == ',') ptr++;
    }
    
    long long result = solution(nums, count);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × d)

Single pass through n numbers, each with d digits, plus constant work per digit

✓ Linear Growth

Space Complexity

O(d)

Array to store digit frequencies for each of d positions

✓ Linear Space

8.5K Views

Medium Frequency

~15 min Avg. Time

235 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler