Maximum Sum of Pairs with Equal Digit Sum – Optimized Approach Using Hash Map and MultiSet
IntuitionThe problem requires finding the maximum sum of two numbers that have the same digit sum. Since numbers can be large, we need an efficient way to categ

## Intuition
The problem requires finding the maximum sum of two numbers that have the same digit sum. Since numbers can be large, we need an efficient way to categorize numbers based on their digit sum and then extract the two largest numbers in each category.

## Approach
1. **Digit Sum Calculation**:  
   - We define a helper function `sumOfDig(n)` to compute the sum of digits of a number.
   
2. **Grouping by Digit Sum**:  
   - We use an `unordered_map<int, multiset<int>>` to group numbers based on their digit sum.  
   - The key is the digit sum, and the value is a `multiset<int>` (ordered collection) to store numbers with the same digit sum.

3. **Finding the Maximum Pair Sum**:  
   - Iterate through each group in the map.
   - If a group contains at least two elements, extract the two largest values and compute their sum.
   - Keep track of the maximum sum found.

## Complexity
- **Time Complexity**:  
  - Computing digit sums for all numbers: O(n * k), where k is the number of digits in each number.
  - Inserting into a multiset: O(log n) per insertion.
  - Extracting the two largest elements from a multiset: O(1) using rbegin().
  - Overall, the complexity is **O(n log n)**.

- **Space Complexity**:  
  - The unordered map stores at most O(n) elements.
  - Each multiset stores at most O(n) elements in the worst case.
  - So, the space complexity is **O(n)**.

## Code
```
class Solution {
public:
    int maximumSum(vector<int>& nums) {
        unordered_map<int , multiset<int>> mp;

        // Group numbers based on their digit sum
        for(int num : nums){
            mp[sumOfDig(num)].insert(num); 
        }

        int ans = -1;
        
        // Find the maximum sum of two numbers with the same digit sum
        for(auto& [key, s] : mp){
            if(s.size() >= 2){
                auto it = s.rbegin();
                ans = max(ans , *it + *(++it));
            }
        }
        return ans;
    }

private:
    int sumOfDig(int n){
        int sum = 0;
        while(n > 0){
            sum += (n % 10);
            n /= 10;
        }
        return sum;
    }
};
```
['Hash Table', 'C++']