Problem Statement in English

You are given an integer array nums. You want to find the greatest sum of a subset of nums such that the sum is divisible by 3.

Approach

To solve the problem of finding the greatest sum of a subset of nums that is divisible by 3, we can use a greedy approach combined with modular arithmetic. The key observations are:

  • The sum of the entire array can be calculated first.
  • If the sum is already divisible by 3, we can return it directly.
  • If the sum is not divisible by 3, we need to adjust it by removing the smallest possible elements that will make the sum divisible by 3.

If the sum modulo 3 is 1, we can either:

  • Remove the smallest element that gives a remainder of 1 when divided by 3.
  • Or remove the two smallest elements that give a remainder of 2 when divided by ``3`.

If the sum modulo 3 is 2, we can either:

  • Remove the smallest element that gives a remainder of 2 when divided by 3.
  • Or remove the two smallest elements that give a remainder of 1 when divided by 3.

Solution in Python


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        hm = defaultdict(list)

        for num in nums:
            hm[num % 3].append(num)

        res = sum(nums)

        if not res % 3:
            return res

        hm[1].sort()
        hm[2].sort()

        if res % 3 == 1:
            remove1 = hm[1][0] if hm[1] else inf
            remove2 = sum(hm[2][:2]) if len(hm[2]) >= 2 else inf
            return res - min(remove1, remove2)
        else:
            remove2 = hm[2][0] if hm[2] else inf
            remove1 = sum(hm[1][:2]) if len(hm[1]) >= 2 else inf
            return res - min(remove1, remove2)

        return res

Complexity

  • Time: $O(n \log n)$
    Since we sort the lists in the hashmap.

  • Space: $O(n)$
    We use extra space to store the numbers in the hashmap.

Mistakes I Made

I was using an additive approach rather than a subtractive approach to find the minimum number to remove to make the sum divisible by 3.

And we are done.