# Calculating and improving time and memory complexity

private static int Sum (int[] a, int from, int to){
int total=0;
for (int i=from; i <= to; i++)
res += a[i];
}

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?
• Consider carefully what happens in these three cases: i=1, j=1; i=1, j=2; i=2, j=1. Jan 1 '15 at 3:49

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.

• 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! Jan 1 '15 at 20:52
• @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? Jan 1 '15 at 20:59
• 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! Jan 1 '15 at 21:15
• @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. Jan 1 '15 at 21:18
• I'm trying to do it step by step.. why is firstOccurence[0] is -1 at the beginning? Jan 1 '15 at 21:38