Continuous Subsequence divisible by a number

Problem Statement: 
      What is the number of sub-sequences divisible by the given divisor  ?  

Given sequence:

                        {1 , 1 , 3 , 2 , 4, 1 ,4 , 5}
Divisor is 5

Answer is 11

Reference : Problem number 3 of
http://www.mii.lt/olympiads_in_informatics/pdf/INFOL062.pdf

Solution: 

Our goal is find the number of continuous sub-sequences divisible by the divisor
We will group the pre-fixes of the given sequence by the remainders (here modulo 5) of the sums of their elements.
If there are 'k'  prefixes for some remainder, then number of continuous sub sequences, with the sums of elements divisible by divisor (here 5) will be given by

ⁿC₂    = k(k-1)/2

 

 

Full Source Code: LINK

Implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

/** * Sub-Routine to count numnber of sub-sequnces * @param d: the given divisor */ public static int solve(int[] arr, int d) { Object o; int Answer = 0; int[] hash = new int[d]; int sum = 0; int val; int num; for (int i = 0; i < arr.length; i++) { num = arr[i]; if(num % d == 0) // count numbers which are divisible by divisor Answer ++ ; sum += num; val = sum % d; if(val<0) //handle negative numbers val = val * (-1); hash[val] = hash[val] + 1; } int size=hash.length ; for (int i = 0; i < size; i++) { int count = hash[i]; if(count > 1) Answer = Answer + count * (count -1)/2 ; } System.out.println(Answer+hash[0]); return Answer+hash[0]; }

Users are requested to refer the reference.
If u liked my article please comment and like the page on facebook.
Happy Coding!! :)