Sunday, June 28, 2015

Count the number of subsequence divisible by 6

You are provided a string with only digits [0 - 9], your task is to count the number of subsequences of string divisible by 6.

For e.g. The given string is 1234566
The subsequences divisible by 6 are 12, 24, 36, 6, 6, 66
Hence the answer should be 6

The most obvious approach which comes is to generate all the subsequences and do a divisibility check and return the count satisfying the condition.

But it is too expensive and overall complexity is 2^n (where n is the size of the string)

Can we make it better?




Obviously the units places has to be even i.e among 2, 4, 6, 8, 0.
So the questions boils down finding the number of subsequences divisible by 3 and units digits as even.

So how can we find the number of subsequences divisible by 3?

Or when does the adding of a number at units place makes it divisible by 3 ?

Lets assume you have a subsequence in hand 
a(1) a(2) a(3) ... a(n) % 3                    =    x                                   (0 <=x <= 2) 
so what if add another digit in front of it making it
a(1) a(2) a(3) ... a(n) a(n + 1) % 3           =    y                             (0 <= y <= 2)
Now if you work out few examples we would get the following table



x
a(n+1)% 3
y
0
0
0
0
1
1
0
2
2
1
0
1
1
1
2
1
2
0
2
0
2
2
1
0
2
2
1

So by looking at the following table we can easily work out the code



#define MOD 1000000007

long long count(char * s) {
 long long len = strlen (s);
 long long ones = 0, twos = 0, threes = 0, ans = 0, t_ones, t_twos, t_threes, sum = 0;
 for (int  i = 0; i < len; i++) {
  int rm = (s[i] - '0') % 3;
  switch (rm) {
   case 0:
    t_ones = (ones + ones) % MOD;
    t_twos = (twos + twos) % MOD;
    t_threes = (threes + threes) % MOD;
    sum = threes + 1;
    ones = t_ones, twos = t_twos, threes = t_threes;
    threes++;
    break;
   case 1:
    t_ones = (ones + threes) % MOD;
    t_twos = (twos + ones) % MOD;
    t_threes = (threes + twos) % MOD;
    sum = twos;
    ones = t_ones, twos = t_twos, threes = t_threes;
    ones++;
    break;
   case 2:
    t_ones = (ones + twos) % MOD;
    t_twos = (twos + threes) % MOD;
    t_threes = (threes + ones) % MOD;
    sum = ones;
    ones = t_ones, twos = t_twos, threes = t_threes;
    twos++;
    break;
  }
  if ((s[i] - '0') % 2 == 0)
   ans = (ans + sum) % MOD;
 }
 return ans;
}

Overall complexity of the algorithm is O(n)

14 comments :

  1. Can you explain in more detail what are ones twos and threes?

    ReplyDelete
  2. if no =217
    say a1=2, a2=1
    x= (a1 a2)%3=(21)%3=0
    remainder a3%3=7%3=1
    y should be 1
    but in table it is 2..
    Can u please make it more clear?

    ReplyDelete
  3. if you can explain this question that would be great

    ReplyDelete
  4. The values in the table were a little messed up, thanks for pointing it out!

    ReplyDelete
  5. Updated the question with an example, let me know if you need any further leads.

    ReplyDelete
  6. ones, twos and threes keep track of the number of subsequences which give 1, 2, 3 respectively as remainder when divided by 3, which can be formed till the ith character of the string.

    ReplyDelete
  7. ok..thanks for acknowledging that...:)

    ReplyDelete
  8. can you please explain these statements ?

    t_ones = (ones + ones) in Case 0

    ReplyDelete
  9. So the case 1 represents a (n + 1) % 3 = 1

    So if we have a look at the 2nd row of the table the new number of subsequences with the remainder 1 will be

    number of subsequences with remainder 1 encountered till now + number of subsequences with remainder 0 encountered till now (this is because now adding the current digit with each of the previous subsequences would generate the subsequence of remainder 1)

    Hence the statement
    t_ones = ones + threes

    Finally sum = threes + 1;

    this is due to counting the subsequences of the single digit (if you notice the equivalent addition to threes is threes++ in line 15)


    Hope this makes a little clear, feel free to reach me out in case of any other issue

    ReplyDelete
  10. thanks for the clarity..

    ReplyDelete
  11. The solution is elegant, but please consider explaining how is your solution designed and more importantly, what variables are tracking/updating what part of your designed solution by commenting your code well (hat-tip to geeksforgeeks), for e.g. 't_ones' is not very obvious to many users.

    ReplyDelete
  12. not getting the desired output please help

    ReplyDelete
  13. Thanks for your inputs! Would update the code with the comments.

    ReplyDelete
  14. Can you provide the test case?

    ReplyDelete