Max Sum of a Pair With Equal Sum of Digits

Max Sum of a Pair With Equal Sum of Digits

What is this problem about?

In this problem, you are given an array of integers. You need to find the maximum possible sum of exactly two numbers from the array that share the exact same sum of their digits. For example, the sum of digits for 18 is $1+8=9$, and for 36 is $3+6=9$. If no two numbers share the same digit sum, return -1.

Why is this asked in interviews?

This is a fantastic Hash Map grouping problem. It is designed to test your ability to map derived properties (the digit sum) to the original values efficiently. Interviewers look to see if you can optimize spatial and temporal complexity. Instead of sorting groups of numbers, a strong candidate will realize they only need to track the absolute maximum number seen so far for each digit sum.

Algorithmic pattern used

This utilizes the Hash Map / Array Grouping pattern. Since the maximum possible digit sum for a standard 32-bit integer is relatively small (e.g., $9+9+9+9+9+9+9+9+9 = 81$), you can use a Hash Map or a fixed-size array of size 82. As you iterate:

1. Calculate the digit sum of the current number.
2. If that digit sum exists in your map, current_number + mapped_number is a valid pair sum. Compare it against your global maximum.
3. Update the map for that digit sum to hold max(mapped_number, current_number).

Example explanation

Array: [18, 43, 36, 13, 7] Map tracks digit_sum -> max_number_seen. Max_Pair_Sum = -1.

• 18: Digit sum 9. Map {9: 18}.
• 43: Digit sum 7. Map {9: 18, 7: 43}.
• 36: Digit sum 9. It's in the map! The stored number is 18. Valid pair sum: 36 + 18 = 54. Max_Pair_Sum = 54. Update map to hold max of 18 and 36. Map {9: 36, 7: 43}.
• 13: Digit sum 4. Map {9: 36, 7: 43, 4: 13}.
• 7: Digit sum 7. In the map! Stored number is 43. Valid pair sum: 7 + 43 = 50. Max_Pair_Sum remains 54. Update map for 7 to max(43, 7) which is 43. The final maximum pair sum is 54.

Common mistakes candidates make

A common error is storing all numbers with the same digit sum in a list inside the Hash Map, and then sorting the list at the end to find the top two numbers. While correct, this wastes memory and introduces $O(K \log K)$ sorting time per group. The problem only asks for the sum of the top two numbers, so you only ever need to hold the single largest number previously seen to pair with the current one.

Interview preparation tip

When an interview question asks for a "pair" based on a shared property, never build full lists of groups. Always store just the "best" historical value in your Hash Map. Processing the array in a single pass while resolving the math on the fly demonstrates highly optimal engineering habits.