Max Sum of a Pair With Equal Sum of Digits
MedPrompt
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 <= 1051 <= nums[i] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
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
maxSumto -1. - Create a helper function
getDigitSum(n)that calculates the sum of digits of a numbern. - Use a nested loop to iterate through all pairs of indices
(i, j)wherei < j. - For each pair, calculate the digit sum for
nums[i]andnums[j]. - If the digit sums are equal, update
maxSum = max(maxSum, nums[i] + nums[j]). - After checking all pairs, return
maxSum.
Walkthrough
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
Time
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
O(1), as we only use a few variables for storage, regardless of the input size.
Trade-offs
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.
A more efficient approach is to avoid the O(N²) pair comparisons by grouping numbers based on their digit sum. A hash map is an ideal data structure for this task.
Algorithm
- Initialize
maxSum = -1. - Create a
Map<Integer, List<Integer>> mapto group numbers by their digit sum. - For each
numinnums:- Calculate its digit sum
s. - Add
numto the list associated with keysin the map.
- Calculate its digit sum
- Iterate through each
listin the map's values:- If the list contains two or more numbers, sort it in descending order.
- Update
maxSum = max(maxSum, list.get(0) + list.get(1)).
- Return
maxSum.
Walkthrough
In this approach, we first iterate through the input array nums once to categorize the numbers. We use a hash map where the keys are the digit sums and the values are lists of numbers that share that digit sum. For each number in nums, we compute its digit sum and add the number to the corresponding list in the map.
After populating the map, we iterate through its values (the lists of numbers). For any list that contains two or more numbers, we know a valid pair can be formed. To find the maximum sum for that specific digit sum group, we need the two largest numbers in that list. We can find these by sorting the list in descending order and taking the first two elements. Their sum is a candidate for the overall maximum sum. We compare this sum with our global maxSum and update it if necessary. If a list has fewer than two elements, it's ignored. Finally, we return the maxSum.
import java.util.*; 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) { Map<Integer, List<Integer>> map = new HashMap<>(); for (int num : nums) { int digitSum = getDigitSum(num); map.computeIfAbsent(digitSum, k -> new ArrayList<>()).add(num); } int maxSum = -1; for (List<Integer> group : map.values()) { if (group.size() >= 2) { Collections.sort(group, Collections.reverseOrder()); maxSum = Math.max(maxSum, group.get(0) + group.get(1)); } } return maxSum; }}Complexity
Time
O(N * log(N) + N * log(M)). Populating the map takes O(N * log(M)). The sorting step is the bottleneck. In the worst case, all N numbers have the same digit sum, leading to sorting a list of size N, which takes O(N * log(N)) time.
Space
O(N), as the hash map may need to store all N numbers from the input array in the worst-case scenario where all numbers have different digit sums or are grouped into a few large lists.
Trade-offs
Pros
Significantly faster than the brute-force approach.
Passes the time limits for the given constraints.
Cons
Requires extra space proportional to the input size.
Sorting each group can be slightly less optimal than a single-pass approach.
This is the most optimal approach, solving the problem in a single pass. It uses a hash map to cleverly keep track of the largest number seen so far for each digit sum, allowing us to find the maximum pair sum on the fly.
Algorithm
- Initialize
maxSum = -1. - Create a
Map<Integer, Integer> mapto storedigitSum -> maxNumber. - For each
numinnums:- Calculate its digit sum
s. - If
map.containsKey(s), it means a pair is found. UpdatemaxSum = max(maxSum, num + map.get(s)). - Update the map with the larger value for the current sum:
map.put(s, max(map.getOrDefault(s, 0), num)).
- Calculate its digit sum
- Return
maxSum.
Walkthrough
The key insight is that for any number num we are processing, to form a maximal pair, we only need to pair it with the largest number seen so far that has the same digit sum. We don't need to store all previous numbers.
We use a hash map where the key is a digit sum and the value is the largest number encountered up to that point with that digit sum. We iterate through the nums array once. For each num:
- Calculate its digit sum,
s. - Check if the map already contains the key
s. If it does, it means we've previously seen at least one number with the same digit sum. The valuemap.get(s)represents the largest of those. We form a pair(num, map.get(s))and update our overallmaxSumwith their sum if it's larger. - After checking for a pair, we must update the map for the key
s. We want to ensure the value stored forsis always the largest number seen for that digit sum. So, we update the map's value for keysto be the maximum of its current value and the current numbernum.
This single-pass process efficiently finds the maximum sum by always pairing the current number with the best possible partner seen so far.
import java.util.HashMap;import java.util.Map; 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) { Map<Integer, Integer> map = new HashMap<>(); int maxSum = -1; for (int num : nums) { int digitSum = getDigitSum(num); if (map.containsKey(digitSum)) { maxSum = Math.max(maxSum, num + map.get(digitSum)); } map.put(digitSum, Math.max(map.getOrDefault(digitSum, 0), num)); } return maxSum; }}Complexity
Time
O(N * log(M)), where N is the number of elements and M is the maximum value in `nums`. We iterate through the array once (O(N)), and for each element, the dominant operation is calculating the digit sum (O(log(M))). Hash map operations take average O(1) time.
Space
O(1). The keys of the map are digit sums. For a number up to 10⁹, the maximum possible digit sum is for 999,999,999, which is 81. Therefore, the map will have at most a small, constant number of keys, making the space usage independent of N.
Trade-offs
Pros
Most efficient in both time and space.
Solves the problem in a single pass over the input array.
Cons
The logic is slightly more complex to reason about compared to brute force.
Solutions
Solution
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; }}class Solution { public: int maximumSum ( vector < int >& nums ) { int d [ 100 ]{}; int ans = - 1 ; for ( int v : nums ) { int x = 0 ; for ( int y = v ; y ; y /= 10 ) { x += y % 10 ; } if ( d [ x ]) { ans = max ( ans , d [ x ] + v ); } d [ x ] = max ( d [ x ], v ); } return ans ; } };class Solution: def maximumSum(self, nums: List[int]) -> int: d = defaultdict(int) ans = - 1 for v in nums: x, y = 0, v while y: x += y % 10 y //= 10 if x in d: ans = max(ans, d[x] + v) d[x] = max(d[x], v) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.