3780. Maximum Sum of Three Numbers Divisible by Three
Medium47.7% acceptance21,901 / 45,872 submissions
Asked by 1 company
Topics
You are given an integer array nums.
Your task is to choose exactly three integers from nums such that their sum is divisible by three.
Return the maximum possible sum of such a triplet. If no such triplet exists, return 0.
Example 1:
Input: nums = [4,2,3,1]
Output: 9
Explanation:
The valid triplets whose sum is divisible by 3 are:
(4, 2, 3)with a sum of4 + 2 + 3 = 9.(2, 3, 1)with a sum of2 + 3 + 1 = 6.
Thus, the answer is 9.
Example 2:
Input: nums = [2,1,5]
Output: 0
Explanation:
No triplet forms a sum divisible by 3, so the answer is 0.
Constraints:
3 <= nums.length <= 1051 <= nums[i] <= 105
Hints
Hint 1
Split numbers into groups by
x % 3.Hint 2
Only four valid combinations for
sum % 3 == 0.Hint 3
Possible combinations are
0 + 0 + 0, 1 + 1 + 1, 2 + 2 + 2, 0 + 1 + 2.Hint 4
Sort groups descending, try each combo using top values.