Find longest subarray whose sum divisible by K

Question

find longest subarray whose sum divisible by K. It is possible in O(n)? If not can it be done in better then n^2 ?

I cant think of anything better then n^2 , tried to do it as we find longest subarray whose sum equals k , but got stuck with some cases in case of if sum is divisible by k — Peter, Oct 26 '12 at 14:42
Just to clarify: by subarray do you mean an array of elements obtained by removing some elements from the original array, or a contiguous sequence of elements from the original array? — IVlad, Oct 26 '12 at 15:02

score 8 · Accepted Answer · answered Oct 26 '12 at 14:53

8

Let s[i] = sum of first i elements modulo K.

We have:

s[i] = (s[i - 1] + a[i]) % K

We have to find, for each i, the smallest j such that s[i] == s[j]. You can find this by hashing the s[i] values. If K is small, you can just keep an array p[i] = first position for which s[k] == i.

The complexity is O(n).

answered Oct 26 '12 at 14:53

IVlad

43,099
13
111
179

1

You need to take special care of the case when `s[i]` itself is divisible by `k`. Correct me if I am wrong – Aman Deep Gautam Oct 26 '12 at 15:39
3

@AmanDeepGautam - I think it depends on implementation. `s[i] < k`, so it's only divisible by `k` when it's 0, a value which first appears outside `s` (`s[-1]` or `s[0]` depending on indexing), which is what the algorithm will find, so if you implement it with this in mind, you shouldn't need to handle it as a special case. – IVlad Oct 26 '12 at 16:40

score 0 · Answer 2 · answered Oct 26 '12 at 14:52

function longestRangeDividableBy(k) {
  arrayOfRanges
  sum =0
  startIndex = 0
  endIndex = 0
  for ( i=0 ; i < array.size; i++) {
    sum += array[i]
    if (sum % k != 0) {
      endindex = i
    } else {
      arrayOfRanges.add(new Range(startIndex, endIndex);
      startIndex = i+1
      sum = 0
    }
  }
  arrayOfRanges.sortDescending();
  return arrayOfRanges.get(0).lengthOfRange()
}

Here I say the search of the ranges is linear. Thus it depends on the sort wether the algorithm is O(n) or n^2. Correct me if I'm wrong, please.

score 0 · Answer 3 · answered Oct 26 '12 at 19:31

As suggested in previous answers, this can be done in O(N) time and space. Those other answers mention hashing and sorting. However, neither is needed for this problem. In following python program that illustrates a one-pass O(N) method, rr is the input array, vb[x] is the index of the first subsum with modular value x, and ve[x] is the index of the last subsum with modular value x. Typical output is shown after the program.

import random
K, N, vmax = 10, 25, 99
rr = [random.randrange(vmax) for x in range(N)]
print 'rr', rr
vb, ve = [-1 for x in range(K)],  [-1 for x in range(K)]
vb[0] = ve[0] = mb = me = ms = s = 0

for i in range(N):
    s = (s + rr[i]) % K
    ve[s] = i+1
    if vb[s] < 0:
        vb[s] = i+1
    if ve[s] - vb[s] > me - mb:
        mb, me, ms = vb[s], ve[s], s

print "Max len is", me-mb, "for rem", ms, "at [", mb,":",me, "], total=", sum(rr[mb:me])

Typical output, for K=10 and N=25:

rr [26, 57, 0, 70, 33, 94, 23, 60, 62, 3, 28, 14, 12, 72, 6, 86, 29, 10, 60, 50, 21, 37, 40, 96, 73]
Max len is 21 for rem 3 at [ 2 : 23 ], total= 810

keeping the first and last index in hash is what the first answer meant , same thing you are doing in vb and ve — Peter, Oct 26 '12 at 20:58
This uses a hash too. You're just using a perfect hash (simple array) because you assume `k` will be small enough for an array with `k` elements to fit in memory, which is not necessarily the case. — IVlad, Oct 27 '12 at 10:42

score 0 · Answer 4 · answered Nov 05 '18 at 06:02

    as rightly pointed out by @IVIad you have to keep a track of the current 
sum modulo k. 
you can write it as s=0
          s=(s+arr1[i])%k 
    after that in a for loop you can use a dictionary and see if the 
s is present in dictionary ; 
if yes then update the length else update the dictionary .
    below is the code.


    def longestsubsarraywithsumdivisiblebyk(arr1,k):
        h={}
        h[0]=-1
        maxlen=0
        s=0
        for i in range(len(arr1)):
            s=(s+arr1[i])%k
            if s in h:
                maxlen=max(maxlen,i-h[s])
            else:
                h[s]=i
        return maxlen

Find longest subarray whose sum divisible by K

4 Answers4

Linked