2342. Max Sum of a Pair With Equal Sum of Digits

Problem

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.

https://leetcode.com/problems/max-sum-of-a-pair-with-equal-sum-of-digits/

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 <= 10⁵
1 <= nums[i] <= 10⁹

Test Cases

1 2	class Solution: def maximumSum(self, nums: List[int]) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([18,43,36,13,7], 54),
    ([10,12,19,14], -1),

    ([279,169,463,252,94,455,423,315,288,64,494,337,409,283,283,477,248,8,89,166,188,186,128], 872),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums, expected):
    assert sol.maximumSum(nums) == expected

Thoughts

先按 “sum of digits of the number” 把 nums 分组，用一个字典记录分组结果。

每组数字只需要保留最大的两个，以便得到这一组数字的最大和，所以字典的值可以用大小不超过 2 的最小堆。

对所有的数字分组之后，遍历所有分组，如果一个分组里有至少两个数字，就可以计算这一组数字的最大和。所有组的最大和取最大即可。

时间复杂度 O(n)，空间复杂度 O(n)。

Code

solution.py

from collections import defaultdict
from heapq import heappush, heappushpop


class Solution:
    def maximumSum(self, nums: list[int]) -> int:
        max2 = lambda a, b: a if a >= b else b
        groups: dict[int, list[int]] = defaultdict(list)
        for num in nums:
            sd = 0
            val = num
            while val > 0:
                sd += val % 10
                val //= 10

            group = groups[sd]
            if not group:
                group.append(num)
            elif len(group) == 1:
                heappush(group, num)
            else:
                heappushpop(group, num)

        max_sum = -1
        for group in groups.values():
            if len(group) > 1:
                max_sum = max2(max_sum, group[0] + group[1])

        return max_sum

反向引用
- 1742. Maximum Number of Balls in a Box

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。