Greatest Sum Divisible by Three - Practice Coding Problems

Greatest Sum Divisible by Three - Problem

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

You can select any subset of elements from the array. The sum of the selected elements must be divisible by 3 to be valid.

Note: An empty subset has sum 0, which is divisible by 3.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,6,5,1,8]

› Output: 18

💡 Note: Select [3,6,1,8] with sum=18. Since 18%3=0, this is valid. This is the maximum possible sum divisible by 3.

Example 2 — All Divisible

$ Input: nums = [4]

› Output: 0

💡 Note: 4%3=1, so we cannot include 4. The only valid subset is empty set with sum=0.

Example 3 — Multiple Valid Combinations

$ Input: nums = [1,2,3,4,5,6]

› Output: 18

💡 Note: Select [3,4,5,6] with sum=18. Alternative: [1,2,3,6] also gives sum=12, but 18 is larger.

Constraints

1 ≤ nums.length ≤ 4 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers [3,6,5,1,8]

Process

Find subset with maximum sum divisible by 3

Output

Maximum sum: 18 (from selecting [3,6,1,8])

Key Takeaway

🎯 Key Insight: Use dynamic programming to track the maximum sum achievable for each remainder state (0, 1, 2)

Asked in

G Google 12 a Amazon 8 f Facebook 6

The key insight is to use dynamic programming to track the maximum achievable sum for each remainder (0, 1, 2) when divided by 3. Best approach uses DP with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subsets	O(2ⁿ × n)	O(1)	Generate all possible subsets and find maximum sum divisible by 3
Dynamic Programming	O(n)	O(1)	Track maximum sum for each possible remainder state (0, 1, 2)
Greedy Approach	O(n log n)	O(n)	Sort numbers by remainder, greedily select to maximize sum while maintaining divisibility

Brute Force - Try All Subsets — Algorithm Steps

Generate all possible subsets using bit manipulation
For each subset, calculate the sum
Check if sum is divisible by 3
Track maximum valid sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Use bit manipulation to generate all 2^n subsets

Calculate Sums

For each subset, calculate the total sum

Check Divisibility

Keep maximum sum that is divisible by 3

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int maxSum = 0;
    
    // Try all possible subsets using bit manipulation
    for (int mask = 0; mask < (1 << numsSize); mask++) {
        int currentSum = 0;
        for (int i = 0; i < numsSize; i++) {
            if (mask & (1 << i)) {
                currentSum += nums[i];
            }
        }
        
        // Check if sum is divisible by 3
        if (currentSum % 3 == 0) {
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
    }
    
    return maxSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int nums[1000];
    int count = 0;
    char* ptr = line + 1; // Skip '['
    
    while (*ptr != ']') {
        if (*ptr >= '0' && *ptr <= '9' || *ptr == '-') {
            nums[count++] = atoi(ptr);
            while (*ptr != ',' && *ptr != ']') ptr++;
        } else {
            ptr++;
        }
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n)

2^n subsets, each taking O(n) time to calculate sum

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track current and maximum sum

✓ Linear Space

52.0K Views

Medium Frequency

~25 min Avg. Time

1.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Subsets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler