Greatest Sum Divisible by Three

Greatest Sum Divisible by Three

What is this problem about?

The Greatest Sum Divisible by Three interview question asks you to find the maximum possible sum of a subset of an integer array such that the sum is exactly divisible by 3. You can choose any number of elements from the array.

Why is this asked in interviews?

Companies like Goldman Sachs and Amazon use this Dynamic Programming coding problem to test your ability to handle states based on remainders (modulo arithmetic). It's a variation of the Knapsack problem where the "capacity" is defined by the modulo operation. It evaluates whether you can track multiple states simultaneously to build up an optimal solution.

Algorithmic pattern used

This problem uses 1D Dynamic Programming with Modulo States.

1. Maintain an array dp of size 3. dp[i] represents the maximum sum achieved so far that yields a remainder of i when divided by 3. Initialize dp = [0, 0, 0].
2. Iterate through each number num in the input array.
3. For each num, calculate what happens when you add it to the existing sums in dp. Create a temporary copy of dp to avoid modifying the array while iterating over it.
4. For each state s in the current dp: new_sum = s + num. Update the corresponding state in the temporary array: temp[new_sum % 3] = max(temp[new_sum % 3], new_sum).
5. The final answer is dp[0].

Example explanation

nums = [3, 6, 5, 1, 8]

1. Start: dp = [0, 0, 0].
2. Add 3: dp = [3, 0, 0].
3. Add 6: dp = [9, 0, 0].
4. Add 5: 5 % 3 = 2. dp = [9, 0, 14] (9+5=14, rem 2).
5. Add 1: 1 % 3 = 1.
   • 9 + 1 = 10 (rem 1).
   • 14 + 1 = 15 (rem 0).
   • dp = [15, 10, 14].
6. Add 8: 8 % 3 = 2.
   • 15 + 8 = 23 (rem 2). max(14, 23) = 23.
   • 10 + 8 = 18 (rem 0). max(15, 18) = 18.
   • 14 + 8 = 22 (rem 1). max(10, 22) = 22.
   • dp = [18, 22, 23]. Result: 18.

Common mistakes candidates make

• In-place Modification: Updating the dp array directly while iterating through its 3 states for a single number. This can cause a number to be added multiple times.
• Greedy Approach: Trying to add all numbers, then subtracting the smallest number(s) that fix the remainder. While possible, the logic is highly error-prone with edge cases.
• Ignoring Zeros: Not handling initialization correctly, where an unreachable state (0 sum before seeing elements) might accidentally be used as a valid base.

Interview preparation tip

Tracking states by modulo (sum % k) is a standard DP pattern. Practice this pattern, as it applies directly to any problem asking for a subset sum divisible by $K$.