Max Sum with Same Digit Sum | HashMap
IntuitionThe goal of the problem is to find two numbers in the given list nums such that the sum of their digits is equal, and among all such pairs, we want to
# Intuition
The goal of the problem is to find two numbers in the given list nums such that the sum of their digits is equal, and among all such pairs, we want to find the pair whose sum is the largest.

# Approach
1. Key Idea: The main insight here is that the sum of digits of two numbers determines if they can form a valid pair (where the sum of digits is the same). We can then **check for pairs** and maximize the sum.

2. Digit Sum Calculation: For each number in the list, we calculate the **sum of its digits**. This is achieved using the while(num > 0) loop, where the remainder (num % 10) gives the last digit of the number, and num /= 10 reduces the number.

3. Map to Track Maximums: We use a map where the **key is the sum of digits** and the **value is the maximum number** with that sum of digits. For each new number in the array:

    -  If we already have a number with the same sum of digits in the map, **we compare the current number** with the number already stored in the map to **find the maximum sum** of both.
    - If the **sum is not present** in the map, we simply **add it** with the current number.
4. Updating the Result: If a valid pair (same digit sum) is found, we calculate the sum of both numbers and update the max variable with the maximum of the current max value and the sum of the pair.

5. Return the Result: After iterating through all the numbers, the variable max will contain the maximum sum of a valid pair, or -1 if no valid pair was found.

# Complexity
- Time complexity: **O(n * log(max number in nums))**, where n is the number of elements in the array, and max number in nums is the largest number in the array.

- Space complexity: **O(n)**, the space complexity is dominated by the HashMap, which can store up to n entries

# Code
```java []
class Solution {
    public int maximumSum(int[] nums) {
        int max = -1;
        //sum of digits, num
        Map<Integer, Integer> mp = new HashMap<>();

        for(int i : nums){
            int num = i;
            int sum = 0;
            while(num > 0){
                sum += (num % 10);
                num /= 10;
            }
            if(mp.containsKey(sum)){
                max = Math.max(max, i + mp.get(sum));
                mp.put(sum, Math.max(i, mp.get(sum)));
            }else{
                mp.put(sum, i);
            }
        }
        return max;
    }
}
```
``` C++ []
class Solution {
public:
    int maximumSum(vector<int>& nums) {
        int maxSum = -1;
        unordered_map<int, int> mp;

        // Iterate through each number in the array
        for (int num : nums) {
            int sum = 0, temp = num;
            
            // Calculate sum of digits
            while (temp > 0) {
                sum += temp % 10;
                temp /= 10;
            }
            
            // If sum already exists in map, check the max sum
            if (mp.find(sum) != mp.end()) {
                maxSum = max(maxSum, num + mp[sum]);
                mp[sum] = max(mp[sum], num);
            } else {
                mp[sum] = num;
            }
        }
        return maxSum;
    }
};

```
``` Python []
class Solution:
    def maximumSum(self, nums):
        max_sum = -1
        digit_sum_map = {}

        # Iterate through each number in the array
        for num in nums:
            # Calculate sum of digits
            digit_sum = sum(int(digit) for digit in str(num))

            # If sum already exists in map, check the max sum
            if digit_sum in digit_sum_map:
                max_sum = max(max_sum, num + digit_sum_map[digit_sum])
                digit_sum_map[digit_sum] = max(digit_sum_map[digit_sum], num)
            else:
                digit_sum_map[digit_sum] = num

        return max_sum
```
['Array', 'Hash Table', 'Python', 'C++', 'Java']