< Back





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

This is a fun one. We're given an array of integers and we're asked to find the maximum sum we can
create with pairs of integers in the list that have the same sum of their digits. So for this, we
have to recall a trick to sum the digits of an interger - involves some modulo math.

After we've remembered that, solving this is trivial. Using the sum of the digits of an integer as
our hashing function, we'll maintain a dictionary to keep track of the largest value we've
encountered for a particular digit hash. As we iterate through all the numbers in the list, if we
find a hash collision, we sum the number currently being inspected with the number we've stored in
the dictionary, maximizing the sums we've seen across the entire iteration.

Finally, we keep the biggest of the two numbers in the hash collision, because we care about
maintaining the largest sum we've seen so far.

The solution is as follows:


  from collections import defaultdict

  class Solution:
      def sumDigits(self, num: int) -> int:
          s = 0
          while num:
              s += num % 10
              num //= 10
          return s

      def maximumSum(self, nums: List[int]) -> int:
          seen = defaultdict(int)
          ans = -1

          for num in nums:
              s = self.sumDigits(num)

              if s in seen:
                  ans = max(ans, num + seen[s])

              seen[s] = max(seen[s], num)

          return ans


_ Time Complexity:

  O(n) - We iterate through the input list once.

_ Space Complexity:

  O(n) - We store at most n values in the seen dictionary.