CODEWITHSUNDEEP
arraysalgorithmdata-structures
Peter
Peter

Reputation: 2759

Find longest subarray whose sum divisible by K

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 ?

Upvotes: 1

Views: 4679

Answers (4)

ravi tanwar
ravi tanwar

Reputation: 618

    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

Upvotes: 0

James Waldby - jwpat7
James Waldby - jwpat7

Reputation: 8701

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

Upvotes: 0

IVlad
IVlad

Reputation: 43477

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).

Upvotes: 8

Kokozaurus
Kokozaurus

Reputation: 639

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.

Upvotes: 0

Related Questions