Max Sum of a Pair With Equal Sum of Digits

medium hash map digits

Problem

Given an array of positive integers nums, you may pick two different indices i and j whose numbers have the same sum of digits. Among all such pairs, return the largest possible value of nums[i] + nums[j]. If no valid pair exists, return -1.

Inputnums = [18, 43, 36, 13, 7]

Output54

18 and 36 both have digit sum 9, giving 18 + 36 = 54. 43 and 7 both have digit sum 7, giving 50. The best is 54.

nums (comma-separated)

def maximum_sum(nums):
    best = {}
    ans = -1
    for x in nums:
        d = sum(int(c) for c in str(x))
        if d in best:
            ans = max(ans, best[d] + x)
            best[d] = max(best[d], x)
        else:
            best[d] = x
    return ans

function maximumSum(nums) {
  const best = new Map();
  let ans = -1;
  for (const x of nums) {
    let d = 0, t = x;
    while (t > 0) { d += t % 10; t = Math.floor(t / 10); }
    if (best.has(d)) {
      ans = Math.max(ans, best.get(d) + x);
      best.set(d, Math.max(best.get(d), x));
    } else {
      best.set(d, x);
    }
  }
  return ans;
}

class Solution {
    public int maximumSum(int[] nums) {
        Map<Integer, Integer> best = new HashMap<>();
        int ans = -1;
        for (int x : nums) {
            int d = 0, t = x;
            while (t > 0) { d += t % 10; t /= 10; }
            if (best.containsKey(d)) {
                ans = Math.max(ans, best.get(d) + x);
                best.put(d, Math.max(best.get(d), x));
            } else {
                best.put(d, x);
            }
        }
        return ans;
    }
}

int maximumSum(vector<int>& nums) {
    unordered_map<int, int> best;
    int ans = -1;
    for (int x : nums) {
        int d = 0, t = x;
        while (t > 0) { d += t % 10; t /= 10; }
        if (best.count(d)) {
            ans = max(ans, best[d] + x);
            best[d] = max(best[d], x);
        } else {
            best[d] = x;
        }
    }
    return ans;
}

Explanation

The obvious approach is to compare every pair of numbers, check whether their digit sums match, and track the best total. That is correct but quadratic. We can do far better by noticing that we never need to know which two numbers form a group — only the two largest values in each digit-sum group.

For any number, its sum of digits is a key (for example 18 and 36 both reduce to 9). We keep a hash map best that maps each digit-sum to the largest number seen so far with that digit-sum.

As we scan the array once, for the current value x we compute its digit-sum d. If d is already in the map, then x can pair with the biggest earlier number in that group, so we try best[d] + x as a candidate answer. Then we update best[d] to be the larger of the two, so future numbers pair against the strongest partner available.

Example: nums = [18, 43, 36, 13, 7]. Digit sums are 9, 7, 9, 4, 7. When 36 arrives, group 9 already holds 18, so the candidate is 18 + 36 = 54. When 7 arrives, group 7 already holds 43, so the candidate is 43 + 7 = 50. The maximum is 54.

Keeping only the running maximum per group means one linear pass solves the whole problem, and we return -1 if no group ever held two numbers.

Time: O(n) Space: O(n)