Skip to content

3780. Maximum Sum of Three Numbers Divisible by Three

Description

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 of 4 + 2 + 3 = 9.
  • (2, 3, 1) with a sum of 2 + 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 <= 105
  • 1 <= nums[i] <= 105

Solutions

Solution 1: Sorting + Grouping + Enumeration

Thinking

Three numbers sum to a multiple of \(3\) iff their residues are \((0,0,0)\), \((1,1,1)\), \((2,2,2)\), or \((0,1,2)\). After grouping by residue and sorting each group descending, we try pairs of groups and take the best available value from the third.

We first sort the array \(\textit{nums}\), then divide the elements in the array into three groups based on their modulo \(3\) results, denoted as \(\textit{g}[0]\), \(\textit{g}[1]\), and \(\textit{g}[2]\). Where \(\textit{g}[i]\) stores all elements that satisfy \(\textit{nums}[j] \bmod 3 = i\).

Next, we enumerate the cases of selecting one element each from \(\textit{g}[a]\) and \(\textit{g}[b]\), where \(a, b \in \{0, 1, 2\}\). Based on the modulo \(3\) results of the two selected elements, we can determine which group the third element should be selected from to ensure that the sum of the triplet is divisible by \(3\). Specifically, the third element should be selected from \(\textit{g}[c]\), where \(c = (3 - (a + b) \bmod 3) \bmod 3\).

For each combination of \((a, b)\), we try to take out the largest element from both \(\textit{g}[a]\) and \(\textit{g}[b]\), then take out the largest element from \(\textit{g}[c]\), calculate the sum of these three elements, and update the answer.

The time complexity is \(O(n \log n)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(O(n)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        nums.sort()
        g = [[] for _ in range(3)]
        for x in nums:
            g[x % 3].append(x)
        ans = 0
        for a in range(3):
            if g[a]:
                x = g[a].pop()
                for b in range(3):
                    if g[b]:
                        y = g[b].pop()
                        c = (3 - (a + b) % 3) % 3
                        if g[c]:
                            z = g[c][-1]
                            ans = max(ans, x + y + z)
                        g[b].append(y)
                g[a].append(x)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int maximumSum(int[] nums) {
        Arrays.sort(nums);
        List<Integer>[] g = new ArrayList[3];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int x : nums) {
            g[x % 3].add(x);
        }
        int ans = 0;
        for (int a = 0; a < 3; a++) {
            if (!g[a].isEmpty()) {
                int x = g[a].remove(g[a].size() - 1);
                for (int b = 0; b < 3; b++) {
                    if (!g[b].isEmpty()) {
                        int y = g[b].remove(g[b].size() - 1);
                        int c = (3 - (a + b) % 3) % 3;
                        if (!g[c].isEmpty()) {
                            int z = g[c].get(g[c].size() - 1);
                            ans = Math.max(ans, x + y + z);
                        }
                        g[b].add(y);
                    }
                }
                g[a].add(x);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int maximumSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> g(3);
        for (int x : nums) {
            g[x % 3].push_back(x);
        }
        int ans = 0;
        for (int a = 0; a < 3; a++) {
            if (!g[a].empty()) {
                int x = g[a].back();
                g[a].pop_back();
                for (int b = 0; b < 3; b++) {
                    if (!g[b].empty()) {
                        int y = g[b].back();
                        g[b].pop_back();
                        int c = (3 - (a + b) % 3) % 3;
                        if (!g[c].empty()) {
                            int z = g[c].back();
                            ans = max(ans, x + y + z);
                        }
                        g[b].push_back(y);
                    }
                }
                g[a].push_back(x);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func maximumSum(nums []int) int {
    sort.Ints(nums)
    g := make([][]int, 3)
    for _, x := range nums {
        g[x%3] = append(g[x%3], x)
    }
    ans := 0
    for a := 0; a < 3; a++ {
        if len(g[a]) > 0 {
            x := g[a][len(g[a])-1]
            g[a] = g[a][:len(g[a])-1]
            for b := 0; b < 3; b++ {
                if len(g[b]) > 0 {
                    y := g[b][len(g[b])-1]
                    g[b] = g[b][:len(g[b])-1]
                    c := (3 - (a+b)%3) % 3
                    if len(g[c]) > 0 {
                        z := g[c][len(g[c])-1]
                        ans = max(ans, x+y+z)
                    }
                    g[b] = append(g[b], y)
                }
            }
            g[a] = append(g[a], x)
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function maximumSum(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const g: number[][] = Array.from({ length: 3 }, () => []);
    for (const x of nums) {
        g[x % 3].push(x);
    }
    let ans = 0;
    for (let a = 0; a < 3; a++) {
        if (g[a].length > 0) {
            const x = g[a].pop()!;
            for (let b = 0; b < 3; b++) {
                if (g[b].length > 0) {
                    const y = g[b].pop()!;
                    const c = (3 - ((a + b) % 3)) % 3;
                    if (g[c].length > 0) {
                        const z = g[c][g[c].length - 1];
                        ans = Math.max(ans, x + y + z);
                    }
                    g[b].push(y);
                }
            }
            g[a].push(x);
        }
    }
    return ans;
}

Comments