Find the longest sequence length whose sum is divisible by 3

Question

I have an exercise that needs to be done with O(n) time complexity, however, I can only solve it with an O(n^2) solution.

You have an array and you need to count the longest contiguous sequence such that it's sum can be divided to 3 without any remainder. For example for array {1,2,3,-4,-1), the function will return 4 because the longest sequence that its sum(0) can be divided to 3 is {2,3,-4,-1}.

My solution O(n^2) is based on arithmetic progression. Is there any way to do it with O(n) complexity?

Please, I only want a clue or a theoretical explanation. Please don't write the full solution :)

Answer 1

Let's take a look at prefix sums. A [L, R] subarray is divisble by 3 if and only if
prefixSum[L - 1] mod 3 = prefixSum[R] mod 3. This observation gives a very simple linear solution(because there are only 3 possible values of a prefix sum mod 3, we can simply find the first and the last one).

For example, if the input array is {1, 2, 3, -4, -1}, the prefix sums are {0, 1, 0, 0, 2, 1}. (there are n + 1 prefix sums because of an empty prefix). Now you can just take a look at the first and last occurrence of 0, 1 and 2.

Answer 2

As a non-CS person, this is interesting. First approach of mine was simply to calc the running sum mod 3. You'll get a sequence of {0,1,2}. Now look for the first and the last 0, the first and the last 1 and the first and the last 2, and compare their respective distances...

Answer 3

Iterate through the array, summing the total as you go. Record the position of the first position where the modulo sum is 0. Also, record the position of he first position where the modulo sum is 1. And, finally, record the position of he first position where the modulo sum is 2.

Do the same thing backwards also, recording the last position where the modulo sum is 0, 1, and 2. That gives three possibilities for the longest sequence - you just check which pair are farthest apart.