Max Sum of a Pair With Equal Sum of Digits

medium LeetCode #2342
array hash-table sorting heap-priority-queue

Description

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.

Example 1:
Input: nums = [18, 43, 36, 13, 7]
Output: 54
Explanation: The pairs (i, j) that satisfy the conditions are:
- (0, 2): digit sum of 18 is 1+8=9, digit sum of 36 is 3+6=9. Sum = 18+36 = 54.
- (1, 4): digit sum of 43 is 4+3=7, digit sum of 7 is 7. Sum = 43+7 = 50.
The maximum sum is 54.

Example 2:
Input: nums = [10, 12, 19, 14]
Output: -1
Explanation: No two numbers have the same digit sum.
- 10: 1+0 = 1
- 12: 1+2 = 3
- 19: 1+9 = 10
- 14: 1+4 = 5
All digit sums are unique, so no valid pair exists.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

Complexity

Show Complexity
  • Time: O(n)
  • Space: O(n)

Hints

Show Hints
Pattern
Hash map grouping by digit sum
Approach
For each number, compute digit sum and check if we've seen that digit sum before. If yes, update max sum. Always keep the largest number for each digit sum.
Complexity
Track max element for each digit sum, update result when finding second element with same digit sum

Solutions

Show PY Solution 
from collections import defaultdict


def solution(nums: list[int]) -> int:
    m = defaultdict(int)
    ans = -1

    for i in range(len(nums)):
        v = nums[i]
        s = 0
        while v:
            s += v % 10
            v //= 10
        # print(nums[i], s)
        if s in m:
            ans = max(ans, nums[i] + nums[m[s]])
            if nums[i] > nums[m[s]]:
                m[s] = i
        else:
            m[s] = i

    return ans