DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

2 1

Greatest Sum Divisible by Three

Given an array nums of integers, we need to find 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^4
  • 1 <= nums[i] <= 10^4

SOLUTION:

import bisect

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        msum = 0
        n = len(nums)
        total = sum(nums)
        if total % 3 == 0:
            return total
        nums.sort()
        paths = [(nums[i], i) for i in range(n)]
        i = 0
        while i < len(paths):
            currsum, curr = paths[i]
            if (total - currsum) % 3 == 0:
                return total - currsum
            for j in range(curr + 1, n):
                bisect.insort(paths, (currsum + nums[j], j))
            i += 1
        return 0
Enter fullscreen mode Exit fullscreen mode

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay