LeetCode 2342. Max Sum of a Pair With Equal Sum of Digits Solution in Java, C++, Python & More | Explanation + Code

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. 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 <= 105
• 1 <= nums[i] <= 109

Solutions

Solution 1: Hash Table

We can use a hash table d to record the maximum value corresponding to each digit sum, and initialize an answer variable ans = -1.

Next, we traverse the array nums. For each number v, we calculate its digit sum x. If x exists in the hash table d, then we update the answer ans = max(ans, d[x] + v). Then update the hash table d[x] = max(d[x], v).

Finally, return the answer ans.

Since the maximum element in nums is 10⁹, the maximum digit sum is 9 × 9 = 81. We can directly define an array d of length 100 to replace the hash table.

The time complexity is O(n × log M), and the space complexity is O(D). Here, n is the length of the array nums, and M and D are the maximum value of the elements in the array nums and the maximum value of the digit sum, respectively. In this problem, M ≤ 10⁹, D ≤ 81.

PythonJavaC++GoTypeScriptRust

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 ans(code-box)

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; } }(code-box)

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; } };(code-box)

func maximumSum(nums []int) int { d := [100]int{} ans := -1 for _, v := range nums { x := 0 for y := v; y > 0; y /= 10 { x += y % 10 } if d[x] > 0 { ans = max(ans, d[x]+v) } d[x] = max(d[x], v) } return ans }(code-box)

function maximumSum(nums: number[]): number { const d: number[] = Array(100).fill(0); let ans = -1; for (const v of nums) { let x = 0; for (let y = v; y; y = (y / 10) | 0) { x += y % 10; } if (d[x]) { ans = Math.max(ans, d[x] + v); } d[x] = Math.max(d[x], v); } return ans; }(code-box)

impl Solution { pub fn maximum_sum(nums: Vec<i32>) -> i32 { let mut d = vec![0; 100]; let mut ans = -1; for &v in nums.iter() { let mut x: usize = 0; let mut y = v; while y > 0 { x += (y % 10) as usize; y /= 10; } if d[x] > 0 { ans = ans.max(d[x] + v); } d[x] = d[x].max(v); } ans } }(code-box)