title: Number of subarrays divisible by k
body: <p>I had the following question in an interview and, in spite of the fact that I gave a working implementation, it wasn't efficient enough. </p>
  
  <blockquote>
    <p>A slice of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q
    &lt; N. A slice (P, Q) of array A is divisible by K if the number A[P] +
    A[P+1] + ... + A[Q−1] + A[Q] is divisible by K.</p>
  </blockquote>
  
  <p>The function I was asked to write, had to return the number of slices divisible by K. The expected time complexity was O(max(N, K)) and space complexity was O(K).</p>
  
  <p>My solution was the simplest, one loop inside another and check every slice: O(n^2)</p>
  
  <p>I have been thinking but I really can't figure out how can I do it in O(max(N, K)). </p>
  
  <p>It may be a variant of the <a href="http://en.wikipedia.org/wiki/Subset_sum_problem">subset sum problem</a>, but I don't know how to count every subarray. </p>
  
  <p>EDIT: Elements in array could be negatives. Here is an example:</p>
  
  <pre><code>A = {4, 5, 0, -2, -3, 1}, K = 5
  
  Function must return 7, because there are 7 subarrays which sums are divisible by 5
  {4, 5, 0, -2, -3, 1}
  {5}
  {5, 0}
  {5, 0, -2, -3}
  {0}
  {0, -2, -3}
  {-2, -3}
  </code></pre>