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
So by looking at the following table we can easily work out the code
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 ?
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)
Can you explain in more detail what are ones twos and threes?
ReplyDeleteif no =217
ReplyDeletesay 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?
if you can explain this question that would be great
ReplyDeleteThe values in the table were a little messed up, thanks for pointing it out!
ReplyDeleteUpdated the question with an example, let me know if you need any further leads.
ReplyDeleteones, 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.
ReplyDeleteok..thanks for acknowledging that...:)
ReplyDeletecan you please explain these statements ?
ReplyDeletet_ones = (ones + ones) in Case 0
So the case 1 represents a (n + 1) % 3 = 1
ReplyDeleteSo 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
thanks for the clarity..
ReplyDeleteThe 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 (hattip to geeksforgeeks), for e.g. 't_ones' is not very obvious to many users.
ReplyDeletenot getting the desired output please help
ReplyDeleteThanks for your inputs! Would update the code with the comments.
ReplyDeleteCan you provide the test case?
ReplyDelete