Find the longest continuum in the array that the sum of the values in the continuum equal to zero modulo 3

Question

I wrote a code that finds the longest continuum in the array that the sum of the values in the continuum equal to zero modulo 3, e.g for the array a[]={2,-3,5,7,-20,7}

We have 2-3+5+7-20=-9 so the output is 5, My problem is the complexity, now it's O(n^3) a bird whispered me that it can be done in O(n)

public class mmn {
public static void main(String[] args)
{
    int a[]={2,-3,5,7,-20,7};
    int r=what(a);
    System.out.println(r);
}
private 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 what(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;
    }

}

Attempt to rewrite in O(n):

import java.util.*;
class Main {
public static void main (String[] args) throws Exception {
// you should use only one Scanner object
Scanner scanner = new Scanner(System.in);
int a[]={3,1,3,1,3,1};
int n=a.length;
int S[]=new int[n];
int i[]=new int[n];
int best;
int sum;

for (int j=0; j<n; j++) {
    S[j]=a[j]%3;
    i[j]=j;// initialize
    //System.out.println(S[j]);
    //System.out.println(i[j]);     
}
best=1;
for (int k=1; k<n; k++) {
    if((S[k-1]+S[k])%3==0) {//checking if we want a longer continuum
        S[k]=S[k-1]+a[k];
        i[k]=i[k-1];
    }    
    if(S[k]<S[best])//check if i should update the better
        best=k-1;
    }
    System.out.println(best);
}
}

Doing it in O(n*n) is easy, but because while extending a subarray, the net sum modulo 3 do not always goes into a particular direction. I think that bird is actually an EAGLE, as how that observed it in O(n) time? — Prem KTiw, Jan 25 '17 at 13:48
You should specify what's wrong with your attempt, otherwise it isn't clear why did you post it here. — default locale, Jan 25 '17 at 13:52

Abdennacer Lachiheb · Answer 1 · 2017-01-25T14:11:39.987

After computing the prefix sum s[] using dynamic programming, then you can iterate over s and store in a new array of pair s[i]%3 in index i such that first indices is the min indices and the second one is the max indeces, so that new array have length 3, then iterate the new array and store the count of 0,1,2, finally iterate that array again, and find max between
(cnt[ 3 - moduloArray[i] ].first - i,cnt[ 3 - moduloArray[i] ].second - i).

גלעד ברקן · Accepted Answer · 2017-01-26T11:10:14.700

1

Here's an illustration of an O(n) algorithm in Python, making one pass over the array. The idea is that dp[i][r] represents the longest sequence, s, ending at index i where (sum s) % 3 = r. Cleary we look for the highest dp[i][0]. We can only augment the sequence for a particular cell if the previous step recorded any length at all for the appropriate modulo result. Since we access only three cells (a constant) on each iteration through the array, the algorithm has O(n) time and space complexity. (Space can be easily adapted to O(1) since we only need the previous three cells at each iteration.)

a = [2,-3,5,7,-20,7]

best = 0
bestIndex = -1

dp = [[0,0,0] for i in range(len(a) + 1)]

for i in range(1,len(a) + 1):
  r = a[i-1] % 3

  for j in range(3):
    canSumToJ = dp[i-1][(3 + j - r) % 3] > 0

    dp[i][j] = max(1 if r == j else 0
                  ,1 + dp[i-1][(3 + j - r) % 3] if canSumToJ else 0)

  bestIndex = i - 1 if dp[i][0] > best else bestIndex
  best = max(best,dp[i][0])

print(best,(bestIndex - best + 1, bestIndex)) # (5, (0, 4))

# dp
# => [[0, 0, 0]
#    ,[0, 0, 1]
#    ,[1, 0, 2]
#    ,[0, 3, 2]
#    ,[3, 1, 4]
#    ,[5, 4, 2]
#    ,[3, 6, 5]]

edited Jan 26 '17 at 11:10

answered Jan 25 '17 at 17:13

גלעד ברקן

23,602
3
25
61

היי גלעד מהו די פי? הפלט אמור להיות אורך הרצף הארוך ביותר שסכומו מתחלק בשלוש ללא שארית – Jan 26 '17 at 05:46
Can someone translate it to Java? please!! – Error 404 Jan 26 '17 at 07:50
@Nehorai הפלט נכתב בשורה האחרונה עם ה'פרינט'. הוספתי את די פי להראות איך החישוב נראה. – גלעד ברקן Jan 26 '17 at 11:21
@Error404 I am not versed in Java but I could write it in JavaScript if you like. It's very simple - the `for` is just a for loop, where `range` is like `i=0; i – גלעד ברקן Jan 26 '17 at 11:26

Eugene · Answer 3 · 2017-01-25T16:51:40.240

For the fun of it:

List<List<Integer>> list = IntStream.range(0, arrayLenght).mapToObj(x -> x)
            .flatMap(i -> IntStream.range(i, arrayLenght)
                    .mapToObj(j -> Arrays.stream(array).skip(i).limit(arrayLenght - j).mapToObj(t -> t)
                            .collect(Collectors.toList())))
            .collect(Collectors.toList());

int result = list.stream().filter(l -> l.stream().collect(Collectors.summingInt(u -> u)) % 3 == 0)
            .max(Comparator.comparing(List::size))
            .map(List::size)
            .orElse(-1);

It probably can be improved even further to use a bit less operations.

But at least it will work for inputs like:

[1,3,3,3,1]

Find the longest continuum in the array that the sum of the values in the continuum equal to zero modulo 3

3 Answers3

Linked