Description

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.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

This problem requires us to find the pair where the sum of those two pairs is largest. These two pairs should also have same sum of digits. We could potentially store digits sum as a key in HashMap and the values can have List of values which have the same sum. Ultimately, we may end up with lots of numbers of with same sum. Finally, we will have to iterate through this map and find the pairs where the sum is greatest.

Instead of storing all numbers with same sum, we could store only those two numbers which makes up largest sum. This way we will have only 2 possible numbers in the HashMap values.

 1class Solution {
 2    public int maximumSum(int[] nums) {
 3        Map<Integer, List<Integer>> sumToNumbersMap = new HashMap<>();
 4        int maxSum = -1;
 5        for (int num: nums) {
 6            int sum = getSumOfDigits(num);
 7            // when making first entry, add the number to the list
 8            if (!sumToNumbersMap.containsKey(sum)) {
 9                List<Integer> list = new ArrayList<>();
10                list.add(num);
11                sumToNumbersMap.put(sum, list);
12            } else {
13                List<Integer> list = sumToNumbersMap.get(sum);
14                if (list.size() == 2) {
15                    // add the pairs which have the biggest sum
16                    int first = list.get(0);
17                    int second = list.get(1);
18                    if (first < num && first < second) {
19                        list.remove(0);
20                        list.add(num);
21                    } else if (second < num) {
22                        list.remove(1);
23                        list.add(num);
24                    }
25                } else {
26                    list.add(num);
27                }
28                maxSum = Math.max(maxSum, list.get(0) + list.get(1));
29            }
30        }
31        return maxSum;
32    }
33
34    private int getSumOfDigits(int num) {
35        int sum = 0;
36        while (num > 0) {
37            int digit = num % 10;
38            sum += digit;
39            num = num / 10;
40        }
41        return sum;
42    }
43}
  • Time Complexity: O(n)
  • Space Complexity: O(n)

Another solution

Another solution is instead of storing the values as the two numbers with highest sum, we can simply store the highest value seen so far. That way we can check if the currentNum + maxSeenSoFar is greater than maxSum. If it is, we just update the maxSum with new value. Everytime, we get a value with the same sum, we have to add maxSeenSoFar with the value of the number which is largest between currentNum and maxSeenSoFar. The sum of two numbers will be the highest only when the numbers themselves are highest.

 1class Solution {
 2    public int maximumSum (int[] nums) {
 3        Map<Integer, Integer> sumToMaxValue = new HashMap<>();
 4        int maxSum = -1;
 5
 6        for (int num: nums) {
 7            int sumOfDigits = getSumOfDigits(num);
 8            if (!sumToMaxValue.containsKey(sumOfDigits)) {
 9                sumToMaxValue.put(sumOfDigits, num);
10            } else {
11                int maxSeenSoFar = sumToMaxValue.get(sumOfDigits);
12                maxSum = Math.max(maxSum, maxSeenSoFar + num);
13                sumToMaxValue.put(sumOfDigits, Math.max(maxSeenSoFar, num));
14            }
15        }
16        return maxSum;
17    }
18
19    private int getSumOfDigits(int num) {
20        int sum = 0;
21        while (num > 0) {
22            int digit = num % 10;
23            sum += digit;
24            num = num / 10;
25        }
26        return sum;
27    }
28}
  • Time Complexity: O(n)
  • Space Complexity: O(n)