# The longest subarray sum divisible by $5$ in $O(n)$ time

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?

• Is there a upper limit on the integers? – Auberon Jun 2 '16 at 21:44
• No there is no upper limit on the integers – Don Fanucci Jun 2 '16 at 21:44
• 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? – Evil Jun 2 '16 at 21:57
• 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? – Mihai Calancea Jun 2 '16 at 21:59
• 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. – D.W. Jun 2 '16 at 22:52

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