# 23.10.2025[1262. Greatest Sum Divisible by Three]

23.10.2025
[1262. Greatest Sum Divisible by Three](https://leetcode.com/problems/greates...) medium
[blog post](https://leetcode.com/problems/greates...)
[substack](https://open.substack.com/pub/dmitrii...)
[youtube](   • # 23.10.2025[1262. Greatest Sum Divisible ...  )





#### Join me on Telegram

https://t.me/leetcode_daily_unstoppab...

#### Problem TLDR

Max sum that %3 #medium

#### Intuition

```j
// add all numbers that are %3
// search the remaining
// they can be %3=1, %3=2
// we need pairs 1+2
// now take max pairs from 1+2
// or tripples from %3=1 is this a choice?
// big_1 big_1 big_1 small_2
// this makes us loose big_1 + big_1 compared to small_2

// what if we take from single sorted list
// big_1 big_2 (take)
// big_2 big_2 (skip) big_2(skip) big_1 big_1 wrong skip

// what if we take from two lists big_1 sorted and big_2 sorted
// take big_1 big_1 big_1 if it is bigger then big_1 big_2

// edge case: 5 2 2 2 so three %3=2 is also %3

// + some big corner case (my not optimal)
// probably case where 111 == 222 == 12 and we have to choose
// is this dp?

// 23 minute, let's look hints: yes it is dp

// 28 minute: MLE

// i have another idea: all sum can be %3==0,1, or 2
// if %3==0 just return sum
// if %3==1 remove smallest %3==1 or two %3==2
// if %3==2 remove smallest %3==2 or two %3==1
```

remove the smallest from sum
only 3 cases possible

#### Approach

another approach is dp: keep three running sums: %3=0,1,2; evaluate where to place

#### Complexity

Time complexity:
$$O(n)$$

Space complexity:
$$O(1)$$

#### Code
https://dmitrysamoylenko.com/2023/07/...