# Max Sum of a Pair With Equal Sum of Digits
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/max-sum-of-a-pair-with-equal-sum-of-digits)
Canonical: https://scaleengineer.com/dsa/problems/max-sum-of-a-pair-with-equal-sum-of-digits
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
---
## Problem
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. If no such pair of indices exists, return -1.

**Example 1:**

**Input:** nums = [18,43,36,13,7]
**Output:** 54
**Explanation:** The pairs (i, j) that satisfy the conditions are:
- (0, 2), both numbers have a sum of digits equal to 9, and their sum is 18 + 36 = 54.
- (1, 4), both numbers have a sum of digits equal to 7, and their sum is 43 + 7 = 50.
So the maximum sum that we can obtain is 54.

**Example 2:**

**Input:** nums = [10,12,19,14]
**Output:** -1
**Explanation:** There are no two numbers that satisfy the conditions, so we return -1.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force Iteration
The most straightforward approach is to check every possible pair of numbers in the array. This method guarantees finding the correct answer but is very slow.
**Time:** O(N² * log(M)), where N is the number of elements in `nums` and M is the maximum value in `nums`. The nested loops result in O(N²) comparisons, and for each number, calculating the digit sum takes O(log(M)) time. · **Space:** O(1), as we only use a few variables for storage, regardless of the input size.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Highly inefficient due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
This approach uses two nested loops to generate every unique pair of numbers from the input array `nums`. For each pair `(nums[i], nums[j])`, we first calculate the sum of digits for each number. A helper function, `getDigitSum`, can be implemented for this purpose. This function repeatedly takes the number modulo 10 to get the last digit and adds it to a running total, then divides the number by 10 to process the next digit, continuing until the number becomes zero. If the two numbers in the pair have an equal sum of digits, we calculate their sum, `nums[i] + nums[j]`, and compare it with a `maxSum` variable that tracks the maximum sum found so far. If the current pair's sum is larger, we update `maxSum`. The initial value of `maxSum` is -1, which is returned if no valid pair is ever found.

```java
class Solution {
    private int getDigitSum(int n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    public int maximumSum(int[] nums) {
        int maxSum = -1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (getDigitSum(nums[i]) == getDigitSum(nums[j])) {
                    maxSum = Math.max(maxSum, nums[i] + nums[j]);
                }
            }
        }
        return maxSum;
    }
}
```
### Algorithm
- Initialize a variable `maxSum` to -1.
- Create a helper function `getDigitSum(n)` that calculates the sum of digits of a number `n`.
- Use a nested loop to iterate through all pairs of indices `(i, j)` where `i < j`.
- For each pair, calculate the digit sum for `nums[i]` and `nums[j]`.
- If the digit sums are equal, update `maxSum = max(maxSum, nums[i] + nums[j])`.
- After checking all pairs, return `maxSum`.

## Grouping by Digit Sum with a Hash Map
A more efficient approach is to avoid the O(N²) pair comparisons by grouping numbers based on their digit sum. A hash map is an ideal data structure for this task.
**Time:** O(N * log(N) + N * log(M)). Populating the map takes O(N * log(M)). The sorting step is the bottleneck. In the worst case, all N numbers have the same digit sum, leading to sorting a list of size N, which takes O(N * log(N)) time. · **Space:** O(N), as the hash map may need to store all N numbers from the input array in the worst-case scenario where all numbers have different digit sums or are grouped into a few large lists.
**Pros:** Significantly faster than the brute-force approach.; Passes the time limits for the given constraints.
**Cons:** Requires extra space proportional to the input size.; Sorting each group can be slightly less optimal than a single-pass approach.
### Explanation
In this approach, we first iterate through the input array `nums` once to categorize the numbers. We use a hash map where the keys are the digit sums and the values are lists of numbers that share that digit sum. For each number in `nums`, we compute its digit sum and add the number to the corresponding list in the map.

After populating the map, we iterate through its values (the lists of numbers). For any list that contains two or more numbers, we know a valid pair can be formed. To find the maximum sum for that specific digit sum group, we need the two largest numbers in that list. We can find these by sorting the list in descending order and taking the first two elements. Their sum is a candidate for the overall maximum sum. We compare this sum with our global `maxSum` and update it if necessary. If a list has fewer than two elements, it's ignored. Finally, we return the `maxSum`.

```java
import java.util.*;

class Solution {
    private int getDigitSum(int n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    public int maximumSum(int[] nums) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int num : nums) {
            int digitSum = getDigitSum(num);
            map.computeIfAbsent(digitSum, k -> new ArrayList<>()).add(num);
        }

        int maxSum = -1;
        for (List<Integer> group : map.values()) {
            if (group.size() >= 2) {
                Collections.sort(group, Collections.reverseOrder());
                maxSum = Math.max(maxSum, group.get(0) + group.get(1));
            }
        }
        return maxSum;
    }
}
```
### Algorithm
- Initialize `maxSum = -1`.
- Create a `Map<Integer, List<Integer>> map` to group numbers by their digit sum.
- For each `num` in `nums`:
  - Calculate its digit sum `s`.
  - Add `num` to the list associated with key `s` in the map.
- Iterate through each `list` in the map's values:
  - If the list contains two or more numbers, sort it in descending order.
  - Update `maxSum = max(maxSum, list.get(0) + list.get(1))`.
- Return `maxSum`.

## Single-Pass with Optimized Hash Map
This is the most optimal approach, solving the problem in a single pass. It uses a hash map to cleverly keep track of the largest number seen so far for each digit sum, allowing us to find the maximum pair sum on the fly.
**Time:** O(N * log(M)), where N is the number of elements and M is the maximum value in `nums`. We iterate through the array once (O(N)), and for each element, the dominant operation is calculating the digit sum (O(log(M))). Hash map operations take average O(1) time. · **Space:** O(1). The keys of the map are digit sums. For a number up to 10⁹, the maximum possible digit sum is for 999,999,999, which is 81. Therefore, the map will have at most a small, constant number of keys, making the space usage independent of N.
**Pros:** Most efficient in both time and space.; Solves the problem in a single pass over the input array.
**Cons:** The logic is slightly more complex to reason about compared to brute force.
### Explanation
The key insight is that for any number `num` we are processing, to form a maximal pair, we only need to pair it with the largest number seen *so far* that has the same digit sum. We don't need to store all previous numbers.

We use a hash map where the key is a digit sum and the value is the largest number encountered up to that point with that digit sum. We iterate through the `nums` array once. For each `num`:
1.  Calculate its digit sum, `s`.
2.  Check if the map already contains the key `s`. If it does, it means we've previously seen at least one number with the same digit sum. The value `map.get(s)` represents the largest of those. We form a pair `(num, map.get(s))` and update our overall `maxSum` with their sum if it's larger.
3.  After checking for a pair, we must update the map for the key `s`. We want to ensure the value stored for `s` is always the largest number seen for that digit sum. So, we update the map's value for key `s` to be the maximum of its current value and the current number `num`.

This single-pass process efficiently finds the maximum sum by always pairing the current number with the best possible partner seen so far.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    private int getDigitSum(int n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    public int maximumSum(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int maxSum = -1;

        for (int num : nums) {
            int digitSum = getDigitSum(num);
            if (map.containsKey(digitSum)) {
                maxSum = Math.max(maxSum, num + map.get(digitSum));
            }
            map.put(digitSum, Math.max(map.getOrDefault(digitSum, 0), num));
        }
        return maxSum;
    }
}
```
### Algorithm
- Initialize `maxSum = -1`.
- Create a `Map<Integer, Integer> map` to store `digitSum -> maxNumber`.
- For each `num` in `nums`:
  - Calculate its digit sum `s`.
  - If `map.containsKey(s)`, it means a pair is found. Update `maxSum = max(maxSum, num + map.get(s))`.
  - Update the map with the larger value for the current sum: `map.put(s, max(map.getOrDefault(s, 0), num))`.
- Return `maxSum`.

# Solutions
### Java

```java
class Solution {
public
  int maximumSum(int[] nums) {
    int[] d = new int[100];
    int ans = -1;
    for (int v : nums) {
      int x = 0;
      for (int y = v; y > 0; y /= 10) {
        x += y % 10;
      }
      if (d[x] > 0) {
        ans = Math.max(ans, d[x] + v);
      }
      d[x] = Math.max(d[x], v);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: int maximumSum ( vector < int >& nums ) { int d [ 100 ]{}; int ans = - 1 ; for ( int v : nums ) { int x = 0 ; for ( int y = v ; y ; y /= 10 ) { x += y % 10 ; } if ( d [ x ]) { ans = max ( ans , d [ x ] + v ); } d [ x ] = max ( d [ x ], v ); } return ans ; } };
```

### Python

```python
class Solution:
    def maximumSum(self, nums: List[int]) -> int: d = defaultdict(int) ans = - 1 for v in nums: x, y = 0, v while y: x += y % 10 y //= 10 if x in d: ans = max(ans, d[x] + v) d[x] = max(d[x], v) return ans

```