2342. Max Sum of a Pair With Equal Sum of Digits

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/max-sum-of-a-pair-with-equal-sum-of-digits
• topics: Hash Table

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.

Idea

• Since digit sums are limited, we can efficiently group numbers by their digit sum and track the two largest numbers per group

Code

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        digit_sum_map = defaultdict(list)
        for i, n in enumerate(nums):
            val = n % 10
            while (n:= n // 10):
                val += n % 10
            if len(digit_sum_map[val]) < 2:
                digit_sum_map[val].append(nums[i])
            # Replace smallest of two elements
            elif (smallest:= min(digit_sum_map[val])) < nums[i]:
                if digit_sum_map[val][0] == smallest:
                    digit_sum_map[val][0] = nums[i]
                else:
                    digit_sum_map[val][1] = nums[i]
        
        return max((sum(v) for _, v in digit_sum_map.items() if len(v) > 1), default = -1)