current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite 
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?
share|improve this question
    
Consider carefully what happens in these three cases: i=1, j=1; i=1, j=2; i=2, j=1. –  Eric Stein Jan 1 at 3:49

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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! –  BinaryJ Jan 1 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? –  kraskevich Jan 1 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! –  BinaryJ Jan 1 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. –  kraskevich Jan 1 at 21:18
    
I'm trying to do it step by step.. why is firstOccurence[0] is -1 at the beginning? –  BinaryJ Jan 1 at 21:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.