Max Sum of a Pair With Equal Sum of Digits

main.md

Question

Approach

I start by defining a helper function digit_sum that calculates the sum of digits for a given number. Then, I create a dictionary sum_map to store the largest number encountered for each digit sum. I then iterate through the list nums, compute the digit sum for each number, and check if that digit sum already exists in sum_map. If it does, I update max_sum with the sum of the current number and the stored maximum number for that digit sum. I also update sum_map to ensure it always holds the largest value for each digit sum.

Finally, I return max_sum, which holds the largest sum found. If no valid pair is found, I return -1.

Implementation

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        def digit_sum(n: int) -> int:
            return sum(int(digit) for digit in str(n))
        
        sum_map = {}
        max_sum = -1
        
        for num in nums:
            d_sum = digit_sum(num)
            if d_sum in sum_map:
                max_sum = max(max_sum, sum_map[d_sum] + num)
                sum_map[d_sum] = max(sum_map[d_sum], num)
            else:
                sum_map[d_sum] = num
        
        return max_sum

Complexities

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