Max Sum of a Pair With Equal Sum of Digits

Medium
1794.

Max Sum of a Pair With Equal Sum of Digits

MediumArrayHash TableSortingHeap (Priority Queue)AmazonGoogle

Max Sum of a Pair With Equal Sum of Digits is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

You are given an array nums of positive integers.

Choose two different indices i != j such that the sum of the digits of nums[i] equals the sum of the digits of nums[j]. Return the maximum value of nums[i] + nums[j] over all such pairs, or -1 if no pair qualifies.

(The values are capped at 5 · 10^8 here — below LeetCode's 10^9 — so that every pair sum fits a 32-bit integer.)

Example 1

Input
nums = [51,42,24,33,9]
Output
93
Explanation
51, 42, 24 and 33 all have digit sum 6; the two largest give 51 + 42 = 93. 9 has digit sum 9 and no partner.

Example 2

Input
nums = [10,12,19,14]
Output
-1
Explanation
The digit sums 1, 3, 10 and 5 are all different.

Example 3

Input
nums = [500000000,50000000]
Output
550000000
Explanation
Both have digit sum 5.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 5 * 10^8
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumSum = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Max Sum of a Pair With Equal Sum of Digits — Solution

Max Sum of a Pair With Equal Sum of Digits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Max Sum of a Pair With Equal Sum of Digits is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Sorting, Heap
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array nums of positive integers.

Choose two different indices i != j such that the sum of the digits of nums[i] equals the sum of the digits of nums[j]. Return the maximum value of nums[i] + nums[j] over all such pairs, or -1 if no pair qualifies.

(The values are capped at 5 · 10^8 here — below LeetCode's 10^9 — so that every pair sum fits a 32-bit integer.)

Example 1

Input: nums = [51,42,24,33,9]
Output: 93
Explanation: 51, 42, 24 and 33 all have digit sum 6; the two largest give 51 + 42 = 93. 9 has digit sum 9 and no partner.

Example 2

Input: nums = [10,12,19,14]
Output: -1
Explanation: The digit sums 1, 3, 10 and 5 are all different.

Example 3

Input: nums = [500000000,50000000]
Output: 550000000
Explanation: Both have digit sum 5.

Constraints

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

Hints for Max Sum of a Pair With Equal Sum of Digits

  1. Hint 1

    Only pairs with the same digit sum compete, so group the numbers by digit sum.

  2. Hint 2

    Within one group, the best pair is its two largest numbers.

  3. Hint 3

    Scan once, keeping the largest number seen so far for each digit sum: each new number pairs with that maximum.

How to solve Max Sum of a Pair With Equal Sum of Digits

Bucket the numbers by digit sum; inside a bucket the best pair is its top two. Keeping just the running maximum per digit sum lets every number be paired with its best partner as it arrives.

Approach

  1. Keep best[s], the largest number seen so far with digit sum s (there are at most 82 sums).
  2. For each x, compute its digit sum s. If best[s] exists, update the answer with best[s] + x.
  3. Set best[s] = max(best[s], x).
  4. Return the answer, or -1 if nothing was paired.

Why it works

For a fixed digit sum, the largest pair sum is the sum of its two largest members. When the second of those two is scanned, best[s] holds the first, so that pair is evaluated; every evaluated pair is valid, so the maximum found is exactly the answer.

Complexity

  • Time — O(n · d) with d the number of digits
  • Space — O(1)

Pitfalls

  • Pairing the largest number with the second-largest overall ignores the digit-sum condition.
  • A group with a single number produces no pair — the answer stays -1 if every group is a singleton.
  • With LeetCode's full 10^9 range the sum overflows a 32-bit int; use 64-bit arithmetic there.

Reference solution

Python

from typing import List

def maximumSum(nums: List[int]) -> int:
    best = [0] * 82
    ans = -1
    for x in nums:
        s, y = 0, x
        while y:
            s += y % 10
            y //= 10
        if best[s] and best[s] + x > ans:
            ans = best[s] + x
        if x > best[s]:
            best[s] = x
    return ans

Java

public static int maximumSum(int[] nums) {
    int[] best = new int[82];
    long ans = -1;
    for (int x : nums) {
        int s = 0;
        for (int y = x; y > 0; y /= 10) s += y % 10;
        if (best[s] > 0) ans = Math.max(ans, (long) best[s] + x);
        best[s] = Math.max(best[s], x);
    }
    return (int) ans;
}

C++

int maximumSum(vector<int>& nums) {
    int best[82] = {0};
    long long ans = -1;
    for (int x : nums) {
        int s = 0;
        for (int y = x; y > 0; y /= 10) s += y % 10;
        if (best[s] > 0) ans = max(ans, (long long)best[s] + x);
        best[s] = max(best[s], x);
    }
    return (int)ans;
}

JavaScript

var maximumSum = function(nums) {
    var best = new Array(82).fill(0);
    var ans = -1;
    for (var i = 0; i < nums.length; i++) {
        var x = nums[i], s = 0, y = x;
        while (y > 0) { s += y % 10; y = Math.floor(y / 10); }
        if (best[s] > 0 && best[s] + x > ans) ans = best[s] + x;
        if (x > best[s]) best[s] = x;
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets