2342. Max Sum of a Pair With Equal Sum of Digits

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:

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

 

Solutions

Solution: Hash Map

• Time complexity: O(10n -> n)
• Space complexity: O(81 -> 1)
  • max sum digits is 999999999: 9 * 9 = 81

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const maximumSum = function (nums) {
  const n = nums.length;
  const sumDigitsMap = new Map();
  let result = -1;

  const sumDigits = num => {
    let result = 0;

    while (num) {
      result += num % 10;
      num = Math.floor(num / 10);
    }
    return result;
  };

  for (let index = 0; index < n; index++) {
    const num = nums[index];
    const sum = sumDigits(num);

    if (sumDigitsMap.has(sum)) {
      const prevNum = nums[sumDigitsMap.get(sum)];

      if (num > prevNum) {
        sumDigitsMap.set(sum, index);
      }

      result = Math.max(num + prevNum, result);
    } else {
      sumDigitsMap.set(sum, index);
    }
  }

  return result;
};