2025-11-23 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 23

Description

Greatest Sum Divisible by Three

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

Solution

class Solution {
public:
  int maxSumDivThree(vector<int>& nums) {
    int minOne = 0;
    int minTwo = 0;
    int sum = 0;
    for(auto num : nums) {
      if(num % 3 == 1) {
        if(minOne) {
          if(minTwo) minTwo = min(minTwo, minOne + num);
          else minTwo = minOne + num;
          minOne = min(minOne, num);
        } else {
          minOne = num;
        }
      } else if(num % 3 == 2) {
        if(minTwo) {
          if(minOne) minOne = min(minOne, minTwo + num);
          else minOne = minTwo + num;
          minTwo = min(minTwo, num);
        } else {
          minTwo = num;
        }
      }
      sum += num;
    }
    if(sum % 3 == 1) return sum - minOne;
    if(sum % 3 == 2) return sum - minTwo;
    return sum;
  }
};

// Accepted
// 43/43 cases passed (1 ms)
// Your runtime beats 89.48 % of cpp submissions
// Your memory usage beats 93.2 % of cpp submissions (28.8 MB)
Algorithm