We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Greatest Sum Divisible by Three

Difficulty: Medium

Problem Description

Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.

Key Insights

  • The sum of elements can be adjusted by selectively removing elements to ensure divisibility by 3.
  • The remainder when dividing by 3 can be 0, 1, or 2, influencing which elements to consider removing.
  • To maximize the sum while ensuring it is divisible by 3, we might need to remove minimal elements with specific remainders.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves calculating the total sum of the array and determining its remainder when divided by 3. Depending on the remainder, we may need to remove elements with the least impact on the total sum.

  1. Calculate the total sum of the array.
  2. If the sum is divisible by 3, return it.
  3. If not, based on the remainder (1 or 2), find the minimal element(s) that can be removed to make the sum divisible by 3.
  4. Adjust the sum accordingly and return the maximum possible sum.

The approach leverages a single pass to compute the sum and additional logic to determine which elements to remove, ensuring efficiency.

Code Solutions

def maxSumDivThree(nums):
    total_sum = sum(nums)
    remainder = total_sum % 3

    if remainder == 0:
        return total_sum

    min_rem1 = float('inf')
    min_rem2 = float('inf')

    for num in nums:
        if num % 3 == 1:
            min_rem1 = min(min_rem1, num)
        elif num % 3 == 2:
            min_rem2 = min(min_rem2, num)

    if remainder == 1:
        option1 = total_sum - min_rem1 if min_rem1 != float('inf') else float('-inf')
        option2 = total_sum - (min_rem2 * 2) if min_rem2 != float('inf') else float('-inf')
        return max(option1, option2)
    else:  # remainder == 2
        option1 = total_sum - min_rem2 if min_rem2 != float('inf') else float('-inf')
        option2 = total_sum - (min_rem1 * 2) if min_rem1 != float('inf') else float('-inf')
        return max(option1, option2)

# Example usage
print(maxSumDivThree([3, 6, 5, 1, 8]))  # Output: 18
← Back to All Questions