Given an array of non negative integers Find the longest continuous sub array which it's sum is divisible by 5.

For example if the array is: [1,3,9,2,1,5,0,1]

A continuous subarray which it's sum is divisible by 5 for example is: [3,9,2,1]

The longest one will be: [3,9,2,1,5, 0]

So the output will be 6.

It is obvious that a simple algorithm for this will be to just run over all the continuous subarrays and check the one with the biggest size but it will be $O(n^2)$. Is there an algorithm in $O(n)$ time which will solve this one?

  • $\begingroup$ Is there a upper limit on the integers? $\endgroup$ – Auberon Jun 2 '16 at 21:44
  • $\begingroup$ No there is no upper limit on the integers $\endgroup$ – Don Fanucci Jun 2 '16 at 21:44
  • 1
    $\begingroup$ Yes there is such algorithm, but the title is misleading. @Auberon it does not matter, because you can do it % 5, or you have asked about this constant? $\endgroup$ – Evil Jun 2 '16 at 21:57
  • 3
    $\begingroup$ Hint: you can write the sum of a continuous subarray as the difference between two partial sums. What properties should these partial sums have for your purpose? $\endgroup$ – Mihai Calancea Jun 2 '16 at 21:59
  • 2
    $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. What have you tried? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. $\endgroup$ – D.W. Jun 2 '16 at 22:52

As hinted by @Mihai Calancea in the comments, you can

  1. Compute prefix sum@wiki of the original array.

  2. Mod 5 ($\%5$) over the new prefix sum array (credited to @EvilJS).

3. Find two same remainders that are farthest apart.

Please fill the details and figure out why each step can be done in linear time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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