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 <= 1051 <= nums[i] <= 109This approach involves using a hash map to collect numbers with the same digit sum as keys and their corresponding numbers as values. Then, for each group (that has more than one number), calculate the maximal possible sum of any two numbers in that group.
This Python function calculates the digit sum of each number and stores numbers in a dictionary keyed by their digit sum. It then checks if each key has multiple numbers, sorts them, and picks the largest two to calculate their sum.
C++
Java
JavaScript
C#
Time Complexity: O(n log k), where n is the number of elements and k is the average length of the list stored in the hash map.
Space Complexity: O(n) for the hash map.
In this approach, instead of sorting within each digit group, use a max heap (priority queue) to track the two largest numbers efficiently. Maintain the largest two numbers seen on-the-fly for each digit sum group.
This Python solution uses a heap to keep track of the top two numbers in each digit group efficiently. Heap operations ensure that the complexity remains lower than sorting.
C++
Java
JavaScript
C#
Time Complexity: O(n log k), where k is typically small, so it's closer to O(n). Space Complexity: O(n) for the hash map.
| Approach | Complexity |
|---|---|
| Approach 1: Hash Map Grouping | Time Complexity: O(n log k), where n is the number of elements and k is the average length of the list stored in the hash map. |
| Approach 2: Optimized Direct Pair Processing | Time Complexity: O(n log k), where k is typically small, so it's closer to O(n). Space Complexity: O(n) for the hash map. |
Max Sum of a Pair With Equal Sum of Digits | 4 Approaches | Leetcode 2342 | codestorywithMIK • codestorywithMIK • 6,503 views views
Watch 9 more video solutions →Practice Max Sum of a Pair With Equal Sum of Digits with our built-in code editor and test cases.
Practice on FleetCode