We can solve the problem by finding the minimum possible sum of numbers which are of the form 3n+1 (call it n1) and minimum possible sum of numbers 3n+2 (call it n2). Suppose the total sum of the numbers is totSum. Consider three cases:
totSum%3 = 0: Our answer is totSumtotSum%3 = 1: Our answer is totSum-n1totSum%3 = 2: Our answer is totSum-n2
The trick lies in finding n1 and n2. At first, you may think that n1 is just the smallest number in the array, say x, such that x%3 = 1 and n2 is the smallest number in the array, say y, such that y%3 = 2. Consider this array: [2, 2, 3]. Here, according to our definition, n1 is not found and n2 = 2. Now, totSum=7 so totSum%3 = 1. What do we do now??
As it turns out, the definition for n1 and n2 are not correct. Consider two number, x and y, where x%3 = 2 and y%3 = 2. Clearly, (x+y)%3 = (x%3 + y%3)%3 = 1. So in the above example, while there is no single number of type 3n+1, the two number 2 and 2 make up to be n1. So the largest sum divisible by 3 would be 7-(2+2)=3.
Similarly, if x%3=1 and y%3=1, (x+y)%3 = 2.
The approach is to iterate the array and keep track of n1 and n2. For each number k in array, if k%3 = 1, we do n2 = min(n2, n1+k) and n1=min(n1, k). If k%3 = 2, we do n1=min(n1, n2+k) and n2=min(n2, k).
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
int n1=10001, n2=10001, totSum=0;
for (int i : nums) {
totSum += i;
if (i%3 == 1) {
n2 = min(n2, n1+i);
n1 = min(n1, i);
}
if (i%3 == 2) {
n1 = min(n1, n2+i);
n2 = min(n2, i);
}
}
if (totSum%3 == 0)
return totSum;
else if (totSum%3 == 1)
return totSum-n1;
return totSum-n2;
}
};
Time complexity: O(n)
Space complexity: (1)