Greatest Sum Divisible by Three

main.md

Question

Approach

To solve this problem, I start by computing the total sum of the array. If the sum is already divisible by 3, then that’s the maximum answer. But if it’s not divisible by 3, I need to remove the smallest possible value that changes the remainder appropriately. So I group numbers based on their remainder when divided by 3—either 0, 1, or 2. If the total sum leaves remainder 1, I can either remove the smallest number with remainder 1, or remove two smallest numbers with remainder 2; I choose the option that removes the smaller total. Similarly, if the sum leaves remainder 2, I either remove the smallest remainder-2 number, or the two smallest remainder-1 numbers.

Implementation

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        total = sum(nums)
        
        r1, r2 = [], []
        for x in nums:
            if x % 3 == 1:
                r1.append(x)
            elif x % 3 == 2:
                r2.append(x)
        
        r1.sort()
        r2.sort()
        
        if total % 3 == 0:
            return total
        
        # If remainder is 1
        if total % 3 == 1:
            option1 = r1[0] if r1 else float('inf')
            option2 = r2[0] + r2[1] if len(r2) >= 2 else float('inf')
            return total - min(option1, option2)
        
        # If remainder is 2
        if total % 3 == 2:
            option1 = r2[0] if r2 else float('inf')
            option2 = r1[0] + r1[1] if len(r1) >= 2 else float('inf')
            return total - min(option1, option2)

Complexities

• Time: O(n logn)
• Space: O(n)