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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3

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 <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Naive

The naive approach involves examining all possible pairs in the nums array. For each pair (nums[i], nums[j]):

  1. Compute the digit sum for both numbers.
  2. Check if their digit sums are the same.
  3. If they are, calculate the pair’s sum (nums[i] + nums[j]), and update the maximum sum accordingly.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def maximumSum(nums):
    n = len(nums)
    max_sum = -1

    # Iterate through every pair (i, j) where i ≠ j
    for i in range(n):
        for j in range(i + 1, n):
            # Calculate the digit sums of nums[i] and nums[j]
            digit_sum_i = sumDigits(nums[i])
            digit_sum_j = sumDigits(nums[j])

            # If digit sums are equal, calculate their sum and update max_sum
            if digit_sum_i == digit_sum_j:
                max_sum = max(max_sum, nums[i] + nums[j])

    return max_sum

def sumDigits(num):
    """Helper function to calculate the sum of digits."""
    digit_sum = 0
    while num > 0:
        digit_sum += num % 10
        num //= 10
    return digit_sum

Complexity

  • ⏰ Time complexity: O(n^2.k), where n is number of elements in nums and k is number of digits in number on average. Because it takes O(n^2) time for nested loops and then O(k) time is taken for each pair.
  • 🧺 Space complexity: O(1)

Method 2 - Using Hashmap

The task is to find the maximum possible sum of two numbers in the array, nums, such that their sum of digits is equal. This boils down to grouping numbers by their sum of digits and finding the two largest numbers in each group, if there are at least two numbers in that group.

Approach

  1. Step 1: Helper Function for Digit Sum - Calculate the sum of digits for a given number. This will be used to group numbers with the same digit sum.
  2. Step 2: Group Numbers by Digit Sum - Use a HashMap (in Java) or defaultdict (in Python) to store numbers based on their sum of digits as the key.
  3. Step 3: Find Max Pair in Each Group - For each sum of digits, check if there are at least two numbers in that group. If so, find the two largest numbers and compute their sum. Keep track of the maximum sum across all groups.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
	public int maximumSum(int[] nums) {
	    Map<Integer, List<Integer>> groups = new HashMap<>();
	
	    // Group numbers by their digit_sum
	    for (int num : nums) {
	        int digitSum = sumDigits(num);
	        groups.putIfAbsent(digitSum, new ArrayList<>());
	        groups.get(digitSum).add(num);
	    }
	    
	    int ans = -1;
	
	    // Iterate through each group
	    for (List<Integer> grp : groups.values()) {
	        if (grp.size() > 1) {
	            // Sort the group in descending order
	            Collections.sort(grp, Collections.reverseOrder());
	            ans = Math.max(ans, grp.get(0) + grp.get(1));
	        }
	    }
	
	    return ans;
	}
    // Helper function to calculate digit sum
    private int sumDigits(int num) {
        int ans = 0;
        while (num > 0) {
            ans += num % 10;
            num /= 10;
        }

        return ans;
    }    
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        def sum_digits(x: int) -> int:
            """Helper function to calculate the sum of digits of x."""
            return sum(int(d) for d in str(x))
        
        groups: defaultdict[int, List[int]] = defaultdict(list)

        # Group numbers by their digit_sum
        for num in nums:
            digit_sum = sum_digits(num)
            groups[digit_sum].append(num)
        
        ans = -1
        
        # Iterate through each group
        for grp in groups.values():
            if len(grp) > 1:
                # Find the two largest numbers in the group
                grp.sort(reverse=True)
                ans = max(ans, grp[0] + grp[1])
        
        return ans

Complexity

  • ⏰ Time complexity: O(n (log n + k)), where n is the number of elements and k is the number of digits in the largest number. - Finding the two largest numbers in each group: O(n) combined.
  • 🧺 Space complexity: O(n) due to space used by the dictionary to group numbers

Method 3 - Two pass and Store just the pair

We don’t need to store all the groups. We can just keep 2 largest numbers. Hence, we can optimize the above code from time O(nlogn) to O(n).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int maximumSum(int[] nums) {
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int n : nums) {
            int digitSum = sumDigits(n);
            groups.computeIfAbsent(digitSum, l -> new ArrayList<>()).add(n);
            Collections.sort(groups.get(digitSum));
            if (groups.get(digitSum).size() > 2) {
                groups.get(digitSum).remove(0);
            }
        }
        int max = -1;
        for (List<Integer> l : groups.values()) {
            if (l.size() == 2) {
                max = Math.max(max, l.get(0) + l.get(1));
            }
        }
        return max;
    }
    private int sumDigits(int num) {
        int ans = 0;
        while (num > 0) {
            ans += num % 10;
            num /= 10;
        }

        return ans;
    }    
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        def sum_digits(num: int) -> int:
            """Helper function to compute the sum of digits of a number."""
            ans = 0
            while num > 0:
                ans += num % 10
                num //= 10
            return ans
        
        groups: Dict[int, List[int]] = defaultdict(list)
        
        for n in nums:
            digit_sum = sum_digits(n)
            groups[digit_sum].append(n)
            
            # Sort the group and maintain only the two largest elements
            groups[digit_sum].sort()
            if len(groups[digit_sum]) > 2:
                groups[digit_sum].pop(0)
        
        max_val = -1
        
        for l in groups.values():
            if len(l) == 2:
                max_val = max(max_val, l[0] + l[1])
        
        return max_val

Complexity

  • ⏰ Time complexity: O(n * k), as now sorting 2 elements takes constant O(2 log 2) time.
  • 🧺 Space complexity: O(n)

Method 4 - One Pass and store the pair

We dont need to run the loop twice to calculate the maximum. We can calculate the maximum in first iteration itself.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int maximumSum(int[] nums) {
        Map<Integer, List<Integer>> groups = new HashMap<>();
        int max = -1;
        for (int num : nums) {
            int digitSum = sumDigits(num);
            groups.computeIfAbsent(digitSum, l -> new ArrayList<>()).add(num);
            List<Integer> list = groups.get(digitSum);
            Collections.sort(list);
            if (list.size() > 2) {
                list.remove(0);
            }
            if (list.size() == 2) {
                max = Math.max(max, list.get(0) + list.get(1));
            }
            
        }
        return max;
    }
    private int sumDigits(int num) {
        int ans = 0;
        while (num > 0) {
            ans += num % 10;
            num /= 10;
        }

        return ans;
    }    
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        def sum_digits(num: int) -> int:
            """Helper function to compute the sum of digits of a number."""
            ans = 0
            while num > 0:
                ans += num % 10
                num //= 10
            return ans
        
        groups = defaultdict(list)  # Store numbers grouped by their digit sums
        max_sum = -1

        for num in nums:
            digit_sum = sum_digits(num)
            groups[digit_sum].append(num)
            groups[digit_sum].sort()  # Sort the group to keep the largest two numbers
            
            # If the group has more than two elements, remove the smallest one
            if len(groups[digit_sum]) > 2:
                groups[digit_sum].pop(0)
            
            # If the group has exactly two elements, calculate their sum
            if len(groups[digit_sum]) == 2:
                max_sum = max(max_sum, groups[digit_sum][0] + groups[digit_sum][1])
        
        return max_sum

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 5 - One pass using max value

To solve the problem in a single pass, we can exploit the fact that the maximum sum of two numbers with the same digit sum will always involve the two largest numbers with that digit sum. The key idea is to:

  1. Keep track of only the largest number encountered so far for each digit sum.
  2. For each new number, check if adding it to the currently stored largest number for the same digit sum gives a new maximum.

This approach ensures that we only ever inspect relevant pairs and avoids unnecessary storage or processing of additional numbers.

Approach:

  1. Digit Sum Calculation:
    • Write a helper method, sumDigits, that computes the sum of the digits of a number. This enables grouping of numbers by their digit sums.
  2. Map Storage:
    • Use a HashMap (or Map) to map each digit sum to the largest number encountered so far with that digit sum.
  3. Iterate Through the Array:
    • For each number in nums, calculate its digit sum.
    • Check the map for an existing entry for this digit sum:
      • If present, compute the sum of the current number and the stored value. Update the result value if this computed sum is larger.
    • Update the map entry for this digit sum with the larger of the current number or the stored value.
  4. Return the Result:
    • After iterating through all elements, the result variable should hold the maximum sum of two numbers with the same digit sum. If no such pair exists, it will remain -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public int maximumSum(int[] nums) {
        int ans = -1;
        Map<Integer, Integer> digitSumToMax = new HashMap<>();

        for (int num : nums) {
            int digitSum = sumDigits(num);

            // Check if a number with this digit sum already exists in the map
            if (digitSumToMax.containsKey(digitSum)) {
                // Calculate the sum of the current number and the largest number with the same digit sum
                ans = Math.max(ans, digitSumToMax.get(digitSum) + num);
            }

            // Update the mapping to keep the larger of the current or previous value for this digit sum
            digitSumToMax.put(digitSum, Math.max(digitSumToMax.getOrDefault(digitSum, 0), num));
        }

        return ans;
    }

    private int sumDigits(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        ans = -1
        digitSumToMax = {}

        for num in nums:
            digit_sum = self.sum_digits(num)

            # Check if a number with this digit sum already exists in the map
            if digit_sum in digitSumToMax:
                # Calculate the sum of the current number and the largest number with the same digit sum
                ans = max(ans, digitSumToMax[digit_sum] + num)

            # Update the mapping to keep the larger of the current or previous value for this digit sum
            digitSumToMax[digit_sum] = max(digitSumToMax.get(digit_sum, 0), num)

        return ans

    def sum_digits(self, num: int) -> int:
        digit_sum = 0
        while num > 0:
            digit_sum += num % 10
            num //= 10
        return digit_sum