29 Nov 2013

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



nC2    = 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!! :)

3 comments:

  1. Hello just wanted to give you a brief heads up
    and 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

    ReplyDelete
  2. i think return value should be return Answer

    ReplyDelete
  3. Answer should be 10 not 11

    ReplyDelete