Greatest Sum Divisible by Three solution and explanation
Google
9 more videos on this problem
Greatest Sum Divisible by Three - Leetcode 1262 - PythonNeetCodeIO · 15:42 · 17K views
Greatest Sum Divisible by Three | Multiple Approaches | Detailed | Leetcode 1262 | codestorywithMIKcodestorywithMIK · 53:15 · 8K views
Greatest sum divisible by 3 - Leetcode 1262 - Dynamic ProgrammingJoey'sTech · 12:01 · 3K views
Leetcode 1262. Greatest Sum Divisible by ThreeElite Code · 34:08 · 922 views
Greatest Sum Divisible by Three | LeetCode 1262 | Greedy & DP SolutionsSanyam IIT Guwahati · 16:03 · 902 views
Daily Leetcode #2063: Nov 23, 2025 - 1262. Greatest Sum Divisible by ThreeProgramming Live with Larry · 6:15 · 797 views
LeetCode 1262 🔥 Greatest Sum Divisible by 3 | Recursion + Memoization DP | Clean & Optimal Logic Study Placement · 15:38 · 792 views
LeetCode 1262 | Greatest Sum Divisible by Three | Approach & SolutionCarlos · 27:29 · 722 views
1262. Greatest Sum Divisible by Three | Leetcode Daily - PythonLeetcode Daily · 9:45 · 388 views
Greatest Sum Divisible by Three, Medium, LeetCode 1262H William Polenz · 10:54 · 362 views
The problem
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
Approach overview
Problem Overview: You are given an integer array and need the maximum possible sum of elements such that the final sum is divisible by 3. You can choose any subset of elements. The challenge is maximizing the total while ensuring the remainder when divided by three equals zero.
Approach 1: Dynamic Programming with Modulo States (O(n) time, O(1) space)
This method tracks the best possible sums for each remainder when divided by three. Maintain a small DP array where dp[r] stores the maximum sum whose modulo with 3 equals r. For every number in the array, update the states by combining the current value with existing sums and adjusting the modulo using (oldRemainder + num) % 3. Only the largest sums for each remainder are kept. Since there are only three states (0, 1, 2), the memory footprint remains constant and updates are fast. This approach effectively builds the best divisible sum incrementally while scanning the array once.
Approach 2: Direct Modulo Adjustment (Greedy) (O(n) time, O(1) space)
Start by computing the total sum of all numbers. If the sum is already divisible by three, that value is the answer. Otherwise, remove the smallest elements necessary to fix the remainder. If the total remainder is 1, remove either one number with remainder 1 or two numbers with remainder 2. If the remainder is 2, remove either one number with remainder 2 or two numbers with remainder 1. Tracking the smallest candidates while iterating the array avoids sorting and keeps the solution linear. This approach uses a greedy observation about minimizing the removed sum to maximize the remaining divisible total.
The DP method is conceptually clean and aligns with problems involving remainder states, which commonly appear in dynamic programming. The greedy adjustment approach is slightly more intuitive once you recognize that only the modulo remainder matters.
Recommended for interviews: The dynamic programming solution is the safest explanation during interviews because it generalizes well to other remainder problems and demonstrates strong DP reasoning. The greedy modulo adjustment solution is equally optimal in O(n) time but relies on recognizing the mathematical property of divisibility by three. Showing the DP reasoning first and then mentioning the greedy optimization signals strong problem‑solving depth.
Approach 1: Dynamic Programming Approach
This approach uses dynamic programming to maintain the maximum sum with each possible remainder modulo 3. The idea is to track sums where the total sum % 3 == 0, 1, or 2, ensuring that the sum maximized at each step can correctly reach a state fully divisible by 3.
def maxSumDivThree(nums):
dp = [0, float('-inf'), float('-inf')]
for num in nums:
next_dp = dp[:]
for i in dp:
next_dp[(i + num) % 3] = max(next_dp[(i + num) % 3], i + num)
dp = next_dp
return dp[0]class Solution {
public int maxSumDivThree(int[] nums) {
int[] dp = new int[]{0, Integer.MIN_VALUE, Integer.MIN_VALUE};
for (int num : nums) {
int[] dpNext = dp.clone();
for (int i = 0; i < 3; i++) {
dpNext[(i + num) % 3] = Math.max(dpNext[(i + num) % 3], dp[i] + num);
}
dp = dpNext;
}
return dp[0];
}
}#include <vector>
#include <algorithm>
int maxSumDivThree(std::vector<int>& nums) {
std::vector<int> dp = {0, INT_MIN, INT_MIN};
for (int num : nums) {
std::vector<int> dpNext = dp;
for (int sum : dp) {
dpNext[(sum + num) % 3] = std::max(dpNext[(sum + num) % 3], sum + num);
}
dp = dpNext;
}
return dp[0];
}function maxSumDivThree(nums) {
let dp = [0, -Infinity, -Infinity];
for (let num of nums) {
let dpNext = dp.slice();
for (let i = 0; i < 3; i++) {
dpNext[(i + num) % 3] = Math.max(dpNext[(i + num) % 3], dp[i] + num);
}
dp = dpNext;
}
return dp[0];
}#include <limits.h>
int maxSumDivThree(int* nums, int numsSize) {
int dp[3] = {0, INT_MIN, INT_MIN};
for (int i = 0; i < numsSize; i++) {
int dpNext[3];
for (int j = 0; j < 3; j++) {
dpNext[j] = dp[j];
}
for (int j = 0; j < 3; j++) {
int newIndex = (dp[j] + nums[i]) % 3;
if (dpNext[newIndex] < dp[j] + nums[i]) {
dpNext[newIndex] = dp[j] + nums[i];
}
}
for (int j = 0; j < 3; j++) {
dp[j] = dpNext[j];
}
}
return dp[0];
}public class Solution {
public int MaxSumDivThree(int[] nums) {
int[] dp = new int[] { 0, int.MinValue, int.MinValue };
foreach (var num in nums) {
int[] dpNext = (int[])dp.Clone();
for (int i = 0; i < 3; ++i) {
dpNext[(i + num) % 3] = Math.Max(dpNext[(i + num) % 3], dp[i] + num);
}
dp = dpNext;
}
return dp[0];
}
}The solution maintains a dynamic programming table (an array of size 3) where each index represents the maximum sum possible with a remainder of 0, 1, and 2 respectively. We iterate over all numbers in the array and update our dp array to track the maximum possible sums with each remainder. At the end, we return dp[0], which is the maximum sum divisible by 3.
Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(1), due to the fixed size of the dp array.
Approach 2: Direct Modulo and Adjustment
This approach calculates the total sum of the array and modifies based on the remainder when divided by 3. If the total is not divisible by 3, it removes the smallest elements whose removal brings the sum to a number divisible by 3.
def maxSumDivThree(nums):
total = sum(nums)
remainder = total % 3
if remainder == 0: return total
others = sorted([x for x in nums if x % 3 == remainder])
minimum = others[0] if others else float('inf')
others = sorted([x for x in nums if x % 3 == (3-remainder)])
if len(others) > 1:
minimum = min(minimum, others[0] + others[1])
return total - minimum if minimum != float('inf') else 0import java.util.*;
class Solution {
public int maxSumDivThree(int[] nums) {
int total = Arrays.stream(nums).sum();
int remainder = total % 3;
if (remainder == 0) return total;
List<Integer> remainderList = new ArrayList<>();
for (int num : nums) {
if (num % 3 == remainder) remainderList.add(num);
}
Collections.sort(remainderList);
int minimum = remainderList.size() > 0 ? remainderList.get(0) : Integer.MAX_VALUE;
remainderList.clear();
for (int num : nums) {
if (num % 3 == (3 - remainder)) remainderList.add(num);
}
Collections.sort(remainderList);
if (remainderList.size() > 1)
minimum = Math.min(minimum, remainderList.get(0) + remainderList.get(1));
return minimum != Integer.MAX_VALUE ? total - minimum : 0;
}
}#include <vector>
#include <algorithm>
class Solution {
public:
int maxSumDivThree(std::vector<int>& nums) {
int total = std::accumulate(nums.begin(), nums.end(), 0);
int remainder = total % 3;
if (remainder == 0) return total;
std::vector<int> others;
for (int num : nums) if (num % 3 == remainder) others.push_back(num);
std::sort(others.begin(), others.end());
int minimum = others.size() > 0 ? others[0] : INT_MAX;
others.clear();
for (int num : nums) if (num % 3 == (3 - remainder)) others.push_back(num);
std::sort(others.begin(), others.end());
if (others.size() > 1)
minimum = std::min(minimum, others[0] + others[1]);
return total - minimum if minimum != INT_MAX else 0;
}
};function maxSumDivThree(nums) {
let total = nums.reduce((a, b) => a + b, 0);
let remainder = total % 3;
if (remainder === 0) return total;
let group = nums.filter(x => x % 3 === remainder).sort((a, b) => a - b);
let minimum = group.length > 0 ? group[0] : Infinity;
group = nums.filter(x => x % 3 === (3 - remainder)).sort((a, b) => a - b);
if (group.length > 1)
minimum = Math.min(minimum, group[0] + group[1]);
return minimum !== Infinity ? total - minimum : 0;
}#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int maxSumDivThree(int* nums, int numsSize) {
int total = 0;
for (int i = 0; i < numsSize; i++)
total += nums[i];
int remainder = total % 3;
if (remainder == 0) return total;
int *others = malloc(sizeof(int) * numsSize);
int j = 0;
for (int i = 0; i < numsSize; i++)
if (nums[i] % 3 == remainder)
others[j++] = nums[i];
qsort(others, j, sizeof(int), compare);
int minimum = j > 0 ? others[0] : INT_MAX;
j = 0;
for (int i = 0; i < numsSize; i++)
if (nums[i] % 3 == (3 - remainder))
others[j++] = nums[i];
qsort(others, j, sizeof(int), compare);
if (j > 1)
minimum = fmin(minimum, others[0] + others[1]);
free(others);
return minimum != INT_MAX ? total - minimum : 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxSumDivThree(int[] nums) {
int total = 0;
foreach (var num in nums) total += num;
int remainder = total % 3;
if (remainder == 0) return total;
List<int> group = new List<int>();
foreach (var num in nums) {
if (num % 3 == remainder) group.Add(num);
}
group.Sort();
int minimum = group.Count > 0 ? group[0] : int.MaxValue;
group.Clear();
foreach (var num in nums) {
if (num % 3 == (3 - remainder)) group.Add(num);
}
group.Sort();
if (group.Count > 1)
minimum = Math.Min(minimum, group[0] + group[1]);
return minimum != int.MaxValue ? total - minimum : 0;
}
}This solution calculates the total sum and handles adjustments based on the sum's remainder when divided by 3. If not divisible, we seek either a single number or two numbers whose effects upon removal yield divisibility by 3.
Time Complexity: O(n log n), due to sorting operations.
Space Complexity: O(n), for additional lists for tracking specific modulo groups.
Approach 3: Dynamic Programming
We define f[i][j] as the maximum sum of several numbers selected from the first i numbers, such that the sum modulo 3 equals j. Initially, f[0][0]=0, and the rest are -infty.
For f[i][j], we can consider the state of the ith number x:
- If we do not select
x, thenf[i][j]=f[i-1][j]; - If we select
x, thenf[i][j]=f[i-1][(j-x bmod 3 + 3)bmod 3]+x.
Therefore, we can get the state transition equation:
$
f[i][j]=max{f[i-1][j],f[i-1][(j-x bmod 3 + 3)bmod 3]+x}
The final answer is f[n][0].
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
Note that the value of f[i][j] is only related to f[i-1][j] and f[i-1][(j-x bmod 3 + 3)bmod 3], so we can use a rolling array to optimize the space complexity, reducing the space complexity to O(1)$.
function maxSumDivThree(nums: number[]): number {
const n = nums.length;
const inf = 1 << 30;
const f: number[][] = Array(n + 1)
.fill(0)
.map(() => Array(3).fill(-inf));
f[0][0] = 0;
for (let i = 1; i <= n; ++i) {
const x = nums[i - 1];
for (let 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];
}func maxSumDivThree(nums []int) int {
n := len(nums)
const inf = 1 << 30
f := make([][3]int, n+1)
f[0] = [3]int{0, -inf, -inf}
for i, x := range nums {
i++
for 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]
}Approach 4: Default Approach
function maxSumDivThree(nums: number[]): number {
const inf = 1 << 30;
const f: number[] = [0, -inf, -inf];
for (const x of nums) {
const g = [...f];
for (let j = 0; j < 3; ++j) {
f[j] = Math.max(g[j], g[(j - (x % 3) + 3) % 3] + x);
}
}
return f[0];
}func maxSumDivThree(nums []int) int {
const inf = 1 << 30
f := [3]int{0, -inf, -inf}
for _, x := range nums {
g := [3]int{}
for j := range f {
g[j] = max(f[j], f[(j-x%3+3)%3]+x)
}
f = g
}
return f[0]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), where n is the number of elements in nums. |
| Direct Modulo and Adjustment | Time Complexity: O(n log n), due to sorting operations. |
| Dynamic Programming | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Modulo States | O(n) | O(1) | General case when reasoning about remainders and subset sums |
| Direct Modulo Adjustment (Greedy) | O(n) | O(1) | When you recognize the remainder property and want a simpler implementation |
Frequently asked questions
Is Greatest Sum Divisible by Three easy or hard?
The problem is classified as Medium difficulty. The implementation is short, but identifying the remainder-state dynamic programming or the greedy adjustment insight requires experience with modular arithmetic and optimization patterns.
Greatest Sum Divisible by Three Python/Java solution
Python and Java implementations typically use the DP remainder array approach. Maintain an array dp[3] where dp[r] represents the largest sum with remainder r. Update it while iterating through the input array and return dp[0] at the end.
How to solve Greatest Sum Divisible by Three in O(n)?
Iterate through the array and maintain the best sums for remainders 0, 1, and 2. For each number, compute new candidate sums and update the remainder states using (currentSum + num) % 3. Because only three states exist, the algorithm runs in linear time and constant memory.
What is the best approach for Greatest Sum Divisible by Three?
The optimal solution uses dynamic programming with three remainder states. Track the largest sum that produces remainder 0, 1, or 2 when divided by three. For each number, update the states using modulo transitions. This runs in O(n) time and O(1) space and guarantees the maximum valid sum.
Is Greatest Sum Divisible by Three asked at Google/Amazon/Meta?
This type of remainder-based dynamic programming problem appears in interviews at companies such as Amazon, Google, and Meta. Interviewers use it to test understanding of DP state transitions, greedy reasoning, and modular arithmetic optimization.
What data structure is used in Greatest Sum Divisible by Three?
Most solutions use a small dynamic programming array of size three to store the best sums for each modulo remainder. The greedy alternative tracks a few minimum values for numbers with remainder 1 and 2 using simple variables.
What is the time complexity of Greatest Sum Divisible by Three?
The optimal algorithms run in O(n) time because the array is processed once. Both the dynamic programming remainder-state method and the greedy modulo-adjustment method maintain constant-size state variables, giving O(1) space complexity.