Max Sum of a Pair With Equal Sum of Digits - Problem

You are given a 0-indexed array nums consisting of positive integers. You can choose two indices i and j, such that i != j, and the sum of digits of the number nums[i] is equal to that of nums[j].

Return the maximum value of nums[i] + nums[j] that you can obtain over all possible indices i and j that satisfy the conditions. If no such pair of indices exists, return -1.

Input & Output

Example 1 — Basic Case

$ Input: nums = [18,43,25,61,52]

› Output: 113

💡 Note: Numbers 61 and 52 both have digit sum 7 (6+1=7, 5+2=7). Their sum 61+52=113 is the maximum possible.

Example 2 — No Valid Pairs

$ Input: nums = [10,12,19,14]

› Output: -1

💡 Note: Digit sums are: 1, 3, 10, 5. All different, so no pairs with equal digit sums exist.

Example 3 — Multiple Groups

$ Input: nums = [23,32,41,14,50]

› Output: 91

💡 Note: Digit sum 5: 23(2+3=5), 32(3+2=5), 41(4+1=5), 14(1+4=5), 50(5+0=5). Maximum pair: 50+41=91.

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to group numbers by their digit sum and find the maximum pair sum within groups having equal digit sums. The optimal approach uses a hash map to track the two largest values for each digit sum in O(n) time with O(k) space where k is the number of unique digit sums.

Common Approaches

✓ Binary Search Answer

⏱️ Time: N/A Space: N/A

Brute Force - Check All Pairs

⏱️ Time: O(n² × d) Space: O(1)

For each pair of indices (i, j) where i ≠ j, calculate the digit sum of nums[i] and nums[j]. If they're equal, update the maximum sum.

Hash Map Optimization

⏱️ Time: O(n × d) Space: O(n)

Use a hash map to group numbers by their digit sum. For each digit sum group, track the two largest values to find the maximum pair sum efficiently.

Single Pass with Max Tracking

⏱️ Time: O(n × d) Space: O(k)

Instead of storing all numbers and sorting, maintain only the two largest values for each digit sum group. This saves space and eliminates the need for sorting.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

int digitSum(int num) {
    int sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

int solution(int* nums, int numsSize) {
    int maxSum = -1;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (digitSum(nums[i]) == digitSum(nums[j])) {
                int currentSum = nums[i] + nums[j];
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
    }
    
    return maxSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[10000];
    int numsSize = 0;
    
    // Find the opening bracket
    char* p = line;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    // Parse numbers
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        
        char* endptr;
        int num = (int)strtol(p, &endptr, 10);
        if (p != endptr) {
            nums[numsSize++] = num;
            p = endptr;
        } else {
            break;
        }
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

486 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