1262. Greatest Sum Divisible by Three
Problem Description
The problem presents a situation where we are given an array of integers, nums
. Our task is to find the maximum sum of elements selected from this array, with the condition that the sum must be divisible by 3. Not all elements of the array are required to be included in the sum, meaning we can select a subset of the array to achieve our goal, and this subset can even be empty.
The value we are looking for is the largest total we can assemble from the numbers in the array that, when divided by 3, does not leave a remainder. This means the total sum % 3 should equal 0. The challenge comes from determining which elements should be chosen to maximize the sum while meeting the divisibility criterion, as the array may contain any integer, positive or negative.
Intuition
The intuition here is to recognize that the remainder when dividing by three can only be 0, 1, or 2. So for any set of numbers, the total sum can leave one of these three remainders. We can leverage this insight to iteratively build up possible sums and track the largest sum for each of the three remainder categories.
To arrive at the solution:
-
We initialize an array,
f
, with three values:0, -inf, -inf
. This array holds the maximum sum that has a remainder of0, 1, and 2
respectively when divided by 3. We start with0
since an empty set has a sum divisible by 3, andāinfinity
for the others as a base case, indicating that there are no sums for those remainders yet. -
We iterate through each number in the input array. For every number
x
, we create a copy off
, calledg
, to keep track of the new sums we compute in this iteration. -
For each possible remainder value (
j = 0, 1, 2
), we consider two options: a) Exclude the current numberx
from the sum. This means the maximum sum for the remainderj
remainsf[j]
. b) Include the current numberx
in the sum. To find which prior sumx
should be added to for the correct remainder, we use the expression(j - x) % 3
. Then we addx
to that prior sum:f[(j - x) % 3] + x
. -
We select the larger of the two options from step 3 for each remainder category and update
g
with this value. -
After considering the current number
x
, we replacef
with the new values ing
to reflect the updated maximum sums. This way,f
always represents the best sums found so far for each remainder category. -
Once we've considered all numbers,
f[0]
will hold the maximum sum divisible by 3.
This dynamic programming solution efficiently computes the largest sum by solving smaller subproblems iteratively and using past solutions to construct new ones.
Learn more about Greedy, Dynamic Programming and Sorting patterns.
Solution Approach
The given Python solution uses dynamic programming to keep track of the maximum sum we can achieve for each of the three possible remainders when dividing the sum by 3, as we iterate through the input array, nums
. The algorithm progressively builds upon previously computed results to reach the final answer.
Algorithm and Data Structures:
-
We start by initializing a list,
f
, with three elements:[0, float('-inf'), float('-inf')]
. This list will hold the maximum sums we can obtain that have a remainder of0
(f[0]
),1
(f[1]
), and2
(f[2]
) when divided by 3. -
We iterate through each element
x
in the input arraynums
. In each iteration, we will decide whether to includex
in our previous maximum sums to possibly get new maximum sums. -
We create a copy of
f
, calledg
, before modifyingf
. This step is crucial because we want to consider every elementx
based on the previous state off
and without being affected by changes made in the current iteration. -
Now for each possible remainder
(j)
in[0, 1, 2]
, we consider both possibilities ā taking the current elementx
or not taking it. We compute this using a loop:for j in range(3): g[j] = max(f[j], f[(j - x) % 3] + x)
We take the maximum between: a)
f[j]
: The previous maximum sum that had a remainder ofj
when divided by three (representing the case where we do not add the current elementx
). b)f[(j - x) % 3] + x
: The sum of the current element and the maximum sum that, when added tox
, will result in a remainder ofj
after division by 3 (representing the case where we do add the current elementx
). -
Finally,
f
is updated tog
after the inner loop to store the new maximum sums for the current iteration. -
After the loop over
nums
is complete,f[0]
holds the maximum sum of elements that is divisible by 3, and sincef
is updated iteratively after considering each element innums
, it contains the global maximum.
Patterns and Techniques:
-
The algorithm uses a bottom-up dynamic programming approach to break the problem down into smaller subproblems that depend on each other, to arrive at the solution to the larger problem.
-
Initialization of the data list
f
withāinfinity
for non-zero remainders is used to indicate that initially, there are no sums that could produce these remainders. -
Modulo operation is used to keep track of the remainders and map them within the range [0, 1, 2] as per the constraints of the problem.
-
The algorithm avoids recalculating sums for each subset by storing the maximum sum for each possible remainder, thus optimizing the runtime.
By maintaining the state of all subproblems and smartly building up to the answer, the given algorithm reaches the correct solution in an efficient manner.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate the solution approach using a small array. Suppose the input array is nums = [3, 6, 5, 1, 8]
. We want to find the maximal sum of its elements that is divisible by 3.
-
We initialize
f
as[0, float('-inf'), float('-inf')]
. This represents the maximal sums with remainders0
,1
, and2
respectively when divided by 3. Initially, the only sum we have that is divisible by 3 is0
, since we haven't included any elements yet. -
We start iterating through
nums
. Forx = 3
(the first element), we create a copy off
, calling itg
. -
Performing the inner loop, we compare the existing sums in
f
with the sums we'd get by addingx
to each. -
For
j = 0
,g[0] = max(f[0], f[(0 - 3) % 3] + 3) = max(0, 0 + 3) = 3
. Forj = 1
,g[1] = max(f[1], f[(1 - 3) % 3] + 3) = max(float('-inf'), 0 + 3) = 3
. Forj = 2
,g[2] = max(f[2], f[(2 - 3) % 3] + 3) = max(float('-inf'), 0 + 3) = 3
.After iterating with
x = 3
,g
is[3, 3, 3]
, so we updatef
to this. -
We then move to
x = 6
and again make a copy off
tog
. We proceed in a similar manner, updatingg[j]
with comparisons betweenf[j]
andf[(j - 6) % 3] + 6
. This step will end up leavingf
unchanged as6
is a multiple of3
and adding it to any subsum inf
will not increase their value becausef
is already optimal from the previous iteration.After iterating with
x = 6
,f
is still[3, 3, 3]
. -
Moving to
x = 5
, making a copy off
tog
, and performing the inner loop, we get:For
j = 0
,g[0] = max(f[0], f[(0 - 5) % 3] + 5) = max(3, 3 + 5) = 8
. Forj = 1
,g[1] = max(f[1], f[(1 - 5) % 3] + 5) = max(3, 3 + 5) = 8
. Forj = 2
,g[2] = max(f[2], f[(2 - 5) % 3] + 5) = max(3, 8 + 5) = 13
.After iterating with
x = 5
,f
becomes[8, 8, 13]
. -
For
x = 1
, we repeat the process and find thatf
can be updated to[8, 14, 13]
after considering this number. -
Lastly, for
x = 8
, we use the similar update rule and end up withf
being[18, 14, 13]
since we can add8
tof[1]
, previously14
, and get a remainder of0
when divided by3
, which updatesf[0]
. -
After considering all elements, the first element of
f
(f[0]
) contains the maximum sum of elements that is divisible by3
, which is18
. That is the final answer.
By following these steps with our input array of nums = [3, 6, 5, 1, 8]
, we have determined that the maximum sum we can obtain from its elements that is divisible by 3
is 18
. The sequence of the elements contributing to this sum can be [3, 6, 1, 8]
or [6, 5, 1, 8]
, both of which give us the sum of 18
.
Solution Implementation
1class Solution:
2 def max_sum_div_three(self, nums: List[int]) -> int:
3 # Initialize a list to store the maximum sums divisible by 0, 1, and 2 respectively.
4 # We start with 0 for the sum divisible by 3 and negative infinity for others as placeholders.
5 max_sums = [0, float('-inf'), float('-inf')]
6
7 # Iterate over each number in the input list.
8 for num in nums:
9 # Create a copy of the current state of max_sums to calculate the new state.
10 new_max_sums = max_sums.copy()
11
12 # Update the new_max_sums for each of the three states (0, 1, and 2).
13 for remainder in range(3):
14 # Calculate the maximum between the current state and the new possible state obtained
15 # by adding the current number `num` and adjusting for the new remainder.
16 new_max_sums[remainder] = max(max_sums[remainder], max_sums[(remainder - num) % 3] + num)
17
18 # Update max_sums to the state we've calculated for this iteration.
19 max_sums = new_max_sums
20
21 # Return the maximum sum that is divisible by 3.
22 return max_sums[0]
23
1class Solution {
2 public int maxSumDivThree(int[] nums) {
3 // Initialize a variable representing an impossible negative value
4 final int INFINITY = 1 << 30;
5
6 // Initialize max sums for each remainder (0, 1, 2)
7 // when dividing by 3. Start with 0 for remainder 0 and
8 // negative infinity for remainders 1 and 2, meaning
9 // they're initially not reachable.
10 int[] maxSums = new int[] {0, -INFINITY, -INFINITY};
11
12 // Loop through each number in the given nums array
13 for (int num : nums) {
14 // Clone current maxSums array to temporary array to store updates
15 int[] newMaxSums = maxSums.clone();
16
17 // For each possible remainder (0, 1, 2)
18 for (int remainder = 0; remainder < 3; ++remainder) {
19 // Update the maximum sum for the current remainder considering
20 // the new number. The max sum is either the current max sum
21 // without the new number or the max sum with remainder equal to
22 // the difference between the current remainder and num % 3,
23 // adjusted to be within the range [0, 2] using modulo, plus the new number.
24 newMaxSums[remainder] = Math.max(maxSums[remainder],
25 maxSums[(remainder - num % 3 + 3) % 3] + num);
26 }
27
28 // Update maxSums array with the computed values for this iteration
29 maxSums = newMaxSums;
30 }
31 // After processing all numbers, return the max sum that is divisible by 3,
32 // which would be stored at index 0
33 return maxSums[0];
34 }
35}
36
1class Solution {
2public:
3 int maxSumDivThree(vector<int>& nums) {
4 const int INF = 1 << 30; // Define a large number to represent infinity.
5 vector<int> dp = {0, -INF, -INF}; // Initialize dp array to store max sums for modulo 3 values (0, 1, 2).
6
7 for (int x : nums) { // Iterate through each number in nums.
8 vector<int> new_dp = dp; // Make a copy of the current state of dp.
9 for (int j = 0; j < 3; ++j) {
10 // Calculate the index for the updated sum in the original dp array.
11 int idx = (j - x % 3 + 3) % 3;
12 // Choose the maximum between not taking the current number (f[j])
13 // and taking the current number (f[idx] + x)
14 new_dp[j] = max(dp[j], dp[idx] + x);
15 }
16 dp = move(new_dp); // Update the dp array with the new values.
17 }
18 return dp[0]; // Return the maximum sum that is divisible by 3.
19 }
20};
21
1function maxSumDivThree(nums: number[]): number {
2 // Define 'inf' as a large number to act as a placeholder for negative infinity.
3 const inf = 1 << 30;
4 // dp array will hold the maximum sum for modulo 0, 1, and 2.
5 const dp: number[] = [0, -inf, -inf];
6
7 // Loop through each number in the input array.
8 for (const num of nums) {
9 // Clone the current state of 'dp'.
10 const nextState = [...dp];
11
12 // Iterate over the 0, 1, and 2 possible sums.
13 for (let i = 0; i < 3; ++i) {
14 // Calculate the index for the updated modulo class after adding 'num'.
15 // Make sure to stay within the bounds of the array by using the modulo operator.
16 // Update the 'dp' entry if a better (larger) sum is found.
17 dp[i] = Math.max(nextState[i], nextState[(i - (num % 3) + 3) % 3] + num);
18 }
19 }
20 // The answer is the maximum sum divisible by 3, which is stored at index 0 after the loop.
21 return dp[0];
22}
23
Time and Space Complexity
The given Python code defines a function maxSumDivThree
that calculates the maximum sum of a subsequence of the input list nums
such that the sum is divisible by 3.
Time Complexity
The time complexity of the code can be determined by looking at the number of iterations and the operations performed within each iteration. We iterate over each element in nums
exactly once, where nums
length is n
. Inside this loop, we perform constant time operations for each of the three possible remainders when an element is divided by 3. Therefore, the time complexity is O(n)
, where n
is the length of the input list nums
.
Space Complexity
The space complexity is determined by the additional space used by the algorithm beyond the input size. We have an array f
of fixed size 3, and a temporary array g
also of fixed size 3. These arrays don't scale with the size of the input; they are used for storing remainders with respect to division by 3. Hence, the space complexity is O(1)
, which means it uses constant additional space regardless of the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!