Max Sum of a Pair With Equal Sum of Digits

Leetcode Problem:

• Max Sum of a Pair With Equal Sum of Digits

Summary

• Find the maximum sum of two numbers in an array where the sum of digits of each number is equal.

Approach

• The approach used is to calculate the sum of digits of each number and store them in a map
• Then, for each sum of digits, find the two numbers in the map that can be added together to get the maximum sum
• If there are multiple pairs, choose the one with the maximum sum.

Complexity

• O(n log n) due to the sorting of the numbers in the map

Explain

• The code first calculates the sum of digits of each number using the digit_sum function
• Then, it stores these sums and their corresponding numbers in a map
• For each sum of digits, it checks if there are already two numbers in the map that can be added together to get a larger sum
• If not, it adds the current number to the map and updates the map if the current number is larger than the one already in the map
• Finally, it iterates over the map to find the maximum sum of two numbers that can be obtained.

Solution Code:

class Solution {
public:
    unordered_map> map;
    int digit_sum(int num){
        int s = 0;
        while(num){
            s += num % 10;
            num /= 10;
        }
        return s;
    }
    int maximumSum(vector& nums) {
        for(int i = 0 ; i < nums.size(); i++){
            int digit = digit_sum(nums[i]);
            if(map[digit].size() < 2){
                map[digit].push_back(nums[i]);
                if(map[digit].size() == 2 && map[digit][0] < map[digit][1]){
                    int t = map[digit][0];
                    map[digit][0] = map[digit][1];
                    map[digit][1] = t;
                }
            } else{
                if(map[digit][0] <= nums[i]){
                    map[digit][1] = map[digit][0];
                    map[digit][0] = nums[i];
                } else{
                    map[digit][1] = max(map[digit][1], nums[i]);
                }
            }
        }
        int ans = -1;
        for(auto iter: map){
            if((iter.second).size() == 2){
                if(ans < (iter.second[0] + iter.second[1])){
                    ans = iter.second[0] + iter.second[1];
                }
            }
        }
        return ans;
    }
};