**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

^{n}C_{2 }= 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!! :)

Hello just wanted to give you a brief heads up

ReplyDeleteand let you know a few of the images aren't loading properly.

I'm not sure why but I think its a linking issue. I've tried

it in two different web browsers and both show the same results.

Feel free to visit my blog virtual dominatrix

i think return value should be return Answer

ReplyDeleteAnswer should be 10 not 11

ReplyDelete