Today’s problem

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

Intuition

In this question, we can simulate the process described in the question, and then get the answer.

Approach

  1. First write a count function that counts the sum of every integer.
  2. Use a dictionary to store the top two values.
  3. Compare the current number with two numbers stored in the dictionary.
  4. Update ans (initialized by -1), note that we need at least two numbers in the dictionary before we can update the answer.

Complexity

  • Time complexity: $O(Nlog(M))$, N is the length of the sequence, M is the maximum number.

  • Space complexity: $O(N)$.

Code

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        def cnt(x):
            res = 0
            while(x > 0):
                res += x % 10
                x //= 10
            return res

        dic = dict()
        ans = -1
        for x in nums:
            nx = cnt(x)
            if nx in dic:
                if x > dic[nx][0]:
                    dic[nx][1] = dic[nx][0]
                    dic[nx][0] = x
                    if dic[nx][1] > 0:
                        ans = max(ans, dic[nx][0] + dic[nx][1])
                elif x > dic[nx][1]:
                    dic[nx][1] = x
                    ans = max(ans, dic[nx][0] + dic[nx][1])
        
            else:
                dic.update({nx: [x, 0]})
        return ans

image.png