Skip to main content
Talentd

Greatest Sum Divisible by Three - Solution & Explanation

MediumArrayDynamic ProgrammingGreedySorting19 min readAsked at: Amazon, Microsoft, Goldman Sachs +4
Practice this problem

Problem Statement

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 * 104
  • 1 <= 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.

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.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting operations.
Space Complexity: O(n), for additional lists for tracking specific modulo groups.

Try this approach in the editor →

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, then f[i][j]=f[i-1][j];
  • If we select x, then f[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)$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

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.

Direct Modulo and Adjustment

Time Complexity: O(n log n), due to sorting operations.
Space Complexity: O(n), for additional lists for tracking specific modulo groups.

Dynamic Programming—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Modulo StatesO(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

Video Solution

Greatest Sum Divisible by Three - Leetcode 1262 - Python • NeetCodeIO • 17,958 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Greatest Sum Divisible by Three with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays