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.

Description Hints 1 Solution Video 15:42

1262. Greatest Sum Divisible by Three

Medium57.1% acceptance7 companies

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 * 10⁴
1 <= nums[i] <= 10⁴

Asked at 7 companies

D. E. Shaw Amazon Goldman Sachs

Google Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Represent the state as DP[pos][mod]: maximum possible sum starting in the position "pos" in the array where the current sum modulo 3 is equal to mod.

15:42

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxSumDivThree(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[3,6,5,1,8]

Input

[4]

Input

[1,2,3,4,4]

Your code is saved on this device.Solution