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^51 <= nums[i] <= 5 * 10^8
Hints for Max Sum of a Pair With Equal Sum of Digits
Hint 1
Only pairs with the same digit sum compete, so group the numbers by digit sum.
Hint 2
Within one group, the best pair is its two largest numbers.
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
- Keep
best[s], the largest number seen so far with digit sums(there are at most 82 sums). - For each
x, compute its digit sums. Ifbest[s]exists, update the answer withbest[s] + x. - Set
best[s] = max(best[s], x). - 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 ansJava
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