A dockyard crane can only perform a balanced triple lift: it hoists exactly three containers at once, and to keep its counterweights synchronized, the combined weight of those three containers must be an exact multiple of three tons. The dock foreman has a manifest of every container weight sitting in the yard and wants to pick any three distinct containers (position doesn't matter, only weight) that maximize the total lifted weight while keeping that total divisible by three. Help the foreman find the heaviest valid triple lift, or determine that no valid triple exists.
n, the number of containers in the yard.n space-separated integers w_1 ... w_n, the weight (in tons) of each container.Print a single integer: the maximum total weight of exactly three containers whose combined weight is divisible by 3. If no three containers achieve a total divisible by 3 (including whenever n < 3), print -1 instead.
Example 1
Input
5 3 6 5 1 8
Expected
15
Explanation
Remainders mod 3 are: 3->0, 6->0, 5->2, 1->1, 8->2. No remainder class has three containers (class 0 has {6,3}, class 1 has {1}, class 2 has {8,5}), so no same-remainder triple is possible. Taking the single largest container from each nonempty class gives 6 + 1 + 8 = 15, whose remainders 0+1+2 sum to a multiple of 3, and this is the best achievable, so the answer is 15.
Example 2
Input
3 1 2 2
Expected
-1
Explanation
With n = 3 there is only one possible triple: 1 + 2 + 2 = 5, which is not divisible by 3. A mixed (0,1,2) triple is also impossible because no container has weight congruent to 0 mod 3 (remainders are 1, 2, 2), and no single remainder class reaches three containers either. No valid triple lift exists, so the answer is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →