title: Count subarrays divisible by K
body: <p>Given a sequence of n positive integers we need to count consecutive sub-sequences whose sum is divisible by k.</p>
  
  <p>Constraints : N is up to 10^6 and each element up to 10^9 and K is up to 100</p>
  
  <p>EXAMPLE : Let N=5 and K=3 and array be 1 2 3 4 1</p>
  
  <p>Here answer is 4</p>
  
  <p>Explanation : there exists, 4 sub-sequences whose sum is divisible by 3, they are</p>
  
  <pre><code>3
  1 2
  1 2 3
  2 3 4
  </code></pre>
  
  <p>My Attempt : </p>
  
  <pre><code>long long int count=0;
  for(int i=0;i&lt;n;i++){
      long long int sum=0;
      for(int j=i;j&lt;n;j++)
      {
          sum=sum+arr[j];
          if(sum%k==0)
          {
              count++;
          }
      }
  }
  </code></pre>
  
  <p>But obviously its poor approach. Can their be better approach for this question? Please help.</p>
  
  <p>Complete Question: <a href="https://www.hackerrank.com/contests/w6/challenges/consecutive-subsequences" rel="noreferrer">https://www.hackerrank.com/contests/w6/challenges/consecutive-subsequences</a></p>