Scanning an array for length of longest sub-array divisible by 3

Question

I'm writing a program that scans an array and produces the length of the longest sub-array containing elements whose sum is divisible by 3. I have worked using the concept from another question here, using the prefix sum concept - scanning first and last sums that by modolu 3 give out 0,1, 2, calculating the difference between each set and returning the biggest one of the three.

I decided to test it using a random array generator. 90% of the time it works but in others it misses correct answer by a few numbers. Any idea what's wrong?

I've included a tester that includes a non-efficient method that does the same thing. Picture included:

Output:

84|4|94|27|85|10|87|11|66|34|66|42|26|65|12|93|14|

array size is: 17

Bad What: 15

My What: 13

Code:

import static java.lang.Math.*;
import java.util.Random;

 public class Q1 {
    public static void main(String args[]) {
        Random rand = new Random();
        int[] a = new int[rand.nextInt(100)];
        for (int i = 0; i < a.length; i++)
        {
            a[i] = rand.nextInt(100);
            System.out.print(a[i] + "|");
        }
        System.out.println();
        System.out.println("array size is: " + a.length);
        System.out.println("Bad What: " + badWhat(a));
        System.out.println("My What: " + what(a));
    }

    public static int what(int[] a) {
        int sumLeft = 0, sumRight = 0;
        int zero, one, two;
        int firstZero = 0, firstOne = 0, firstTwo = 0, lastZero = 0, lastOne = 0, lastTwo = 0;
        for (int i = 0; i < a.length; i++) {
            sumLeft += negMod(a[i])%3;
            sumRight += negMod(a[a.length - 1 - i]%3);
            if ((sumLeft) % 3 == 0)
                firstZero = i;
                if ((sumRight) % 3 == 0)
                    lastZero = i;
                if ((sumLeft) % 3 == 1)
                    firstOne = i;
                if ((sumRight) % 3 == 1)
                    lastOne = i;
                if ((sumLeft) % 3 == 2)
                    firstTwo = i;
                if ((sumRight) % 3 == 2)
                    lastTwo = i;
            }
        firstOne++;
        firstTwo++;
        zero = lastZero - firstZero + 1;
        one = lastOne - firstOne;
        two = lastTwo - firstTwo;
        int result = max(max(zero, one), two);
        if (firstZero +1 > result)
            result = ++firstZero;
        return result;
    }

    public static int negMod (int a)
    {
        if (a<0)
        {
            return (a+3);
        }
        return a;
    }

    public static int f (int[] a, int low, int high)
    {
        int res = 0;
        for (int i = low; i<=high; i++)
            res += a[i];
        return res;
    }

    public static int badWhat (int[] a)
    {
        int temp = 0;
        for (int i =0; i< a.length; i++) {
            for (int j = i; j < a.length; j++) {
                int c = f(a, i, j);
                if (c % 3 == 0) {
                    if (j - i + 1 > temp)
                        temp = j - i + 1;
                }
            }
        }
        return temp;
    }
}

Answer 1

One obvious mistake is that instead of sumLeft += negMod(a[i] % 3); you have sumLeft += negMod(a[i])%3;.

It appears you have a lot of problems in your algorithm. First of all, in sumRight you should contain sum of elements from the first to the current one, but what you contained was sum from the current to the last one. So, it was just a good luck that your solution worked for some tests.

Secondly, you should find the first subarray with a particular modulo and the last one. So, you don't need to overwrite the value once it is found.

This should work:

public static int what(int[] a) {
    if (a.length == 0) {
        return 0;
    }

    int sumLeft = 0, sumRight = 0;
    for (int el : a) {
        sumRight += el % 3;
    }
    sumRight = negMod(sumRight % 3);

    int firstZero = a.length, firstOne = a.length, firstTwo = a.length,
            lastZero = -1, lastOne = -1, lastTwo = -1;
    for (int i = 0; i < a.length + 1; i++) {
        if (sumLeft % 3 == 0 && firstZero == a.length)
            firstZero = i;
        if (sumRight % 3 == 0 && lastZero == -1)
            lastZero = a.length - 1 - i;
        if (sumLeft % 3 == 1 && firstOne == a.length)
            firstOne = i;
        if (sumRight % 3 == 1 && lastOne == -1)
            lastOne = a.length - 1 - i;
        if (sumLeft % 3 == 2 && firstTwo == a.length)
            firstTwo = i;
        if (sumRight % 3 == 2 && lastTwo == -1)
            lastTwo = a.length - 1 - i;
        sumLeft += negMod(a[min(i, a.length - 1)] % 3);
        sumRight = negMod(sumRight - a[max(a.length - 1 - i, 0)] % 3);
    }
    int zero = lastZero - firstZero + 1;
    int one = lastOne - firstOne + 1;
    int two = lastTwo - firstTwo + 1;
    Integer[] options = new Integer[]{zero, one, two, 0};
    return Collections.max(Arrays.asList(options));
}