Greatest Sum Divisible by Three
MedPrompt
Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.
Example 1:
Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).Example 2:
Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.Example 3:
Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).
Constraints:
1 <= nums.length <= 4 * 1041 <= nums[i] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores all possible subsets of the nums array using recursion (backtracking). For each subset, it calculates the sum of its elements. If the sum is divisible by three, it is compared with the maximum sum found so far. This method guarantees finding the correct answer by checking every possibility, but it is highly inefficient.
Algorithm
- Initialize a global variable
maxSum = 0. - Define a recursive function
solve(index, currentSum). - Base Case: If
indexreaches the end of the array (nums.length):- Check if
currentSumis divisible by 3. - If it is, update
maxSum = max(maxSum, currentSum). - Return from the function.
- Check if
- Recursive Step: For the element at the current
index:- Make a recursive call including the element:
solve(index + 1, currentSum + nums[index]). - Make another recursive call excluding the element:
solve(index + 1, currentSum).
- Make a recursive call including the element:
- Start the process by calling
solve(0, 0). - After the recursion completes, return
maxSum.
Walkthrough
We can implement this using a recursive helper function, say solve(index, currentSum). The function explores two branches at each step: one where the current number nums[index] is included in the sum, and one where it's excluded. The base case for the recursion is when we have considered all numbers (i.e., index reaches the end of the array). At this point, we check if the currentSum is divisible by 3. If it is, we update our global maximum answer. The initial call would be solve(0, 0).
class Solution { int maxSum = 0; public int maxSumDivThree(int[] nums) { solve(0, 0, nums); return maxSum; } private void solve(int index, int currentSum, int[] nums) { if (index == nums.length) { if (currentSum % 3 == 0) { maxSum = Math.max(maxSum, currentSum); } return; } // Option 1: Include nums[index] solve(index + 1, currentSum + nums[index], nums); // Option 2: Exclude nums[index] solve(index + 1, currentSum, nums); }}Complexity
Time
O(2^N), where N is the number of elements in `nums`. For each element, we have two choices (include or exclude), leading to `2^N` possible subsets to check.
Space
O(N), where N is the number of elements in `nums`. This space is used by the recursion stack.
Trade-offs
Pros
Simple to understand and implement the logic.
Guaranteed to find the correct solution by exploring all possibilities.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
This approach uses dynamic programming to efficiently solve the problem. We maintain an array that keeps track of the maximum sum achievable for each possible remainder modulo 3 (0, 1, and 2). We iterate through the numbers in the input array and update these maximum sums at each step. This avoids redundant calculations and provides a linear time solution.
Algorithm
- Initialize a DP array
dpof size 3, wheredp[i]will store the maximum sum found so far that has a remainder ofiwhen divided by 3. Initializedp = [0, 0, 0]. - Iterate through each number
numin the input arraynums. - Inside the loop, create a temporary copy of the
dparray, let's call ittempDp. - For each
prevSumintempDp:- Calculate the
newSum = prevSum + num. - Find the remainder of the new sum:
rem = newSum % 3. - Update the
dparray:dp[rem] = Math.max(dp[rem], newSum).
- Calculate the
- After iterating through all numbers, the value
dp[0]will hold the maximum possible sum that is divisible by 3. - Return
dp[0].
Walkthrough
We use an array, dp, of size 3. dp[i] will store the largest sum we can form that has a remainder of i when divided by 3. We initialize dp as [0, 0, 0].
We iterate through each number num in the nums array. For each num, we calculate the potential new sums by adding num to the existing sums stored in dp. To ensure that we use the sums from the previous step for our calculations, we create a temporary copy of the dp array before performing updates for the current num.
For each of the three possible previous sums (for remainders 0, 1, and 2), we add the current num, find the new remainder, and update the corresponding entry in our main dp array if the new sum is larger. After processing all numbers, dp[0] will contain the maximum sum that is divisible by 3.
class Solution { public int maxSumDivThree(int[] nums) { int[] dp = new int[3]; // dp[0] = max sum with remainder 0 // dp[1] = max sum with remainder 1 // dp[2] = max sum with remainder 2 for (int num : nums) { int[] tempDp = new int[3]; tempDp[0] = dp[0]; tempDp[1] = dp[1]; tempDp[2] = dp[2]; for (int prevSum : tempDp) { int currentSum = prevSum + num; int remainder = currentSum % 3; dp[remainder] = Math.max(dp[remainder], currentSum); } } return dp[0]; }}Complexity
Time
O(N), where N is the number of elements in `nums`. We iterate through the array once, and for each element, we perform a constant number of operations.
Space
O(1), as we only use a constant amount of extra space for the `dp` array of size 3.
Trade-offs
Pros
Highly efficient with linear time complexity.
Uses constant extra space, making it suitable for large inputs.
It's a standard DP pattern that can be applied to similar problems.
Cons
The state transition logic might be slightly less intuitive to grasp initially compared to a direct mathematical formula.
This is the most optimal approach, based on a mathematical insight. The idea is to first calculate the sum of all numbers. If this sum is already divisible by 3, it's our answer. If not, we must remove some numbers to make the sum divisible by 3. To maximize the final sum, we should remove the number or combination of numbers with the smallest possible sum that corrects the remainder. This can be done in a single pass.
Algorithm
- Initialize
totalSum = 0. - Initialize variables to track the two smallest numbers with remainder 1 (
min1_rem1,min2_rem1) and remainder 2 (min1_rem2,min2_rem2). Set them to a value larger than any possible input, likeInteger.MAX_VALUE. - Iterate through
numinnums:- Add
numtototalSum. - If
num % 3 == 1, update the two smallest remainder-1 numbers. - If
num % 3 == 2, update the two smallest remainder-2 numbers.
- Add
- Calculate the remainder of the total sum:
rem = totalSum % 3. - If
rem == 0, returntotalSum. - If
rem == 1:- Calculate the sum after removing the smallest remainder-1 number.
- Calculate the sum after removing the two smallest remainder-2 numbers.
- Return the maximum of these two options. If neither removal is possible, the answer is 0.
- If
rem == 2:- Calculate the sum after removing the smallest remainder-2 number.
- Calculate the sum after removing the two smallest remainder-1 numbers.
- Return the maximum of these two options. If neither removal is possible, the answer is 0.
Walkthrough
First, we calculate the total sum of all elements in nums. Let this be totalSum. The core idea depends on totalSum % 3:
- If
totalSum % 3 == 0: The sum is already perfect. The answer istotalSum. - If
totalSum % 3 == 1: We need to remove a sub-sum that is1 mod 3. To get the largest remaining sum, we must remove the smallest possible value. The options are:- Remove the single smallest number where
num % 3 == 1. - Remove the two smallest numbers where
num % 3 == 2(since(2 + 2) % 3 = 1).
- Remove the single smallest number where
- If
totalSum % 3 == 2: We need to remove a sub-sum that is2 mod 3. The options are:- Remove the single smallest number where
num % 3 == 2. - Remove the two smallest numbers where
num % 3 == 1(since(1 + 1) % 3 = 2).
- Remove the single smallest number where
We can find the totalSum and the necessary smallest numbers (two with remainder 1, two with remainder 2) in a single pass through the array. Then, we apply the logic above to find the maximum possible sum.
class Solution { public int maxSumDivThree(int[] nums) { int totalSum = 0; int min1_rem1 = Integer.MAX_VALUE, min2_rem1 = Integer.MAX_VALUE; int min1_rem2 = Integer.MAX_VALUE, min2_rem2 = Integer.MAX_VALUE; for (int num : nums) { totalSum += num; if (num % 3 == 1) { if (num < min1_rem1) { min2_rem1 = min1_rem1; min1_rem1 = num; } else if (num < min2_rem1) { min2_rem1 = num; } } else if (num % 3 == 2) { if (num < min1_rem2) { min2_rem2 = min1_rem2; min1_rem2 = num; } else if (num < min2_rem2) { min2_rem2 = num; } } } int rem = totalSum % 3; if (rem == 0) { return totalSum; } int ans = 0; if (rem == 1) { if (min1_rem1 != Integer.MAX_VALUE) { ans = Math.max(ans, totalSum - min1_rem1); } if (min2_rem2 != Integer.MAX_VALUE) { ans = Math.max(ans, totalSum - min1_rem2 - min2_rem2); } } else { // rem == 2 if (min1_rem2 != Integer.MAX_VALUE) { ans = Math.max(ans, totalSum - min1_rem2); } if (min2_rem1 != Integer.MAX_VALUE) { ans = Math.max(ans, totalSum - min1_rem1 - min2_rem1); } } return ans; }}Complexity
Time
O(N), as we iterate through the `nums` array only once to compute the sum and find the smallest required numbers.
Space
O(1), as we only use a few variables to store the total sum and the smallest numbers, regardless of the input size.
Trade-offs
Pros
The most efficient solution with O(N) time and O(1) space.
The logic is direct and based on a clear mathematical property, potentially leading to faster execution due to fewer operations per element compared to the DP approach.
Cons
The logic requires careful handling of edge cases, such as when the required numbers for removal do not exist in the array.
Solutions
Solution
class Solution { public int maxSumDivThree ( int [] nums ) { int n = nums . length ; final int inf = 1 << 30 ; int [][] f = new int [ n + 1 ][ 3 ]; f [ 0 ][ 1 ] = f [ 0 ][ 2 ] = - inf ; for ( int i = 1 ; i <= n ; ++ i ) { int x = nums [ i - 1 ]; for ( int j = 0 ; j < 3 ; ++ j ) { f [ i ][ j ] = Math . max ( f [ i - 1 ][ j ], f [ i - 1 ][( j - x % 3 + 3 ) % 3 ] + x ); } } return f [ n ][ 0 ]; } }class Solution { public: int maxSumDivThree ( vector < int >& nums ) { int n = nums . size (); const int inf = 1 << 30 ; int f [ n + 1 ][ 3 ]; f [ 0 ][ 0 ] = 0 ; f [ 0 ][ 1 ] = f [ 0 ][ 2 ] = - inf ; for ( int i = 1 ; i <= n ; ++ i ) { int x = nums [ i - 1 ]; for ( int j = 0 ; j < 3 ; ++ j ) { f [ i ][ j ] = max ( f [ i - 1 ][ j ], f [ i - 1 ][( j - x % 3 + 3 ) % 3 ] + x ); } } return f [ n ][ 0 ]; } };class Solution : def maxSumDivThree ( self , nums : List [ int ]) -> int : n = len ( nums ) f = [[ - inf ] * 3 for _ in range ( n + 1 )] f [ 0 ][ 0 ] = 0 for i , x in enumerate ( nums , 1 ): for j in range ( 3 ): f [ i ][ j ] = max ( f [ i - 1 ][ j ], f [ i - 1 ][( j - x ) % 3 ] + x ) return f [ n ][ 0 ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.