Max Sum of a Pair With Equal Sum of Digits

MEDIUM

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. 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 <= 10⁵
1 <= nums[i] <= 10⁹

Approaches

Checkout 3 different approaches to solve Max Sum of a Pair With Equal Sum of Digits. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables for storage, regardless of the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Max Sum of a Pair With Equal Sum of Digits. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Max Sum of a Pair With Equal Sum of Digits

Algorithms:

Sorting

Data Structures:

ArrayHash TableHeap (Priority Queue)