Calculating and improving time and memory complexity

Question

private static int Sum (int[] a, int from, int to){
 int total=0;
 for (int i=from; i <= to; i++)
 res += a[i];
 return total;
}
public static int Method3 (int []a){
 int temp=0;
 for (int i=0; i <= a.length; i++)
 {
 for (int j=0; j <= a.length; j++)
 {
 int c = Sum(a,i,j);
 if (c%3 == 0)
 {
 if (j-i+1 > temp)
 temp = j-i+1;
 }
 }
 }
return temp;
}

The purpose of Method3 method is to find the longest combination of a given array numbers', so that the sum of the numbers of the combination can be divided by 3 without remainder.

1. How do I make it more efficient in terms of both time and memory complexity?
2. How do I even approach to something like this?
3. ow can I know that the complexity I've reached is the best possible?

• Eric Stein: Consider carefully what happens in these three cases: i=1, j=1; i=1, j=2; i=2, j=1.

Answer 1

It is possible to make it much more efficient by using a completely different algorithm. The idea is to take a closer look at prefix sums. Let's assume that a subarray [L, R] is divisible by 3. It means that prefixSum[R] - prefixSum[L - 1] == 0 (mod 3), or prefixSum[R] == prefixSum[L - 1] (mod 3). It results in a simple solution: iterating over all elements of the array from left to right and maintaining the current prefix sum modulo 3 and keeping track of the first occurrence of each value modulo 3. The code can look like this:

int getLongestSubarray(int[] a) {
 int[] firstOccurrence = new int[3];
 firstOccurrence[0] = -1;
 firstOccurrence[1] = a.length;
 firstOccurrence[2] = a.length;
 int prefixSum = 0;
 int result = 0;
 for (int i = 0; i < a.length; i++) {
 prefixSum = (prefixSum + a[i]) % 3;
 if (prefixSum < 0)
 prefixSum += 3;
 result = Math.max(result, i - firstOccurrence[prefixSum]);
 firstOccurrence[prefixSum] = Math.min(firstOccurrence[prefixSum], i);
 }
 return result;
}

The time complexity is O(n) and the space complexity is O(1). It is optimal because it is not possible to find the longest subarray divisble by 3 without seeing all elements of the input array.

• BinaryJ: At first I thought I understood it, but looking at it carefully now made me realize I haven't fully gotten the idea behind your algorithm. Can you please explain it to me again? Thank you very much!
• kraskevich: @BinaryJ The idea: take a look at prefix sums. sum(l, r) = prefixSum(r) - prefixSum(l - 1). Now we want to find a zero modulo 3. It means that prefixSum(r) == prefixSum(l - 1) modulo 3. If you have any questions, could you please tell me which specific part of this algorithm you do not fully understand?
• BinaryJ: I think I understand the idea, just having a bit of a hard time fully understanding the implementation part, though. More precisely, the last part where you set values to result and firstOccurence. Also, if the array is {1,2,3,4}, doesn't the iteration only checks 1, 1+2 , 1+2+3 and 1+2+3+4 ? for example, for the combination 3+4, does it cover that possibility as well? Again, thank you very much!
• kraskevich: @BinaryJ For {1, 2, 3, 4} the prefix sums(modulo 3) are {1, 0, 0, 1}. firstOccurrence = {-1, 0, 4}(because 2 never appears). 3 + 4 is not checked(it is not divisible, anyway), but 2 + 3 + 4 is checked.
• BinaryJ: I'm trying to do it step by step.. why is firstOccurence[0] is -1 at the beginning?