PROBLEM LINK:
Problem statement:
You are given a very big number(1e5 digits in the worst case) in Base 10 representation. You have to find out the number of sub-sequences of digits which are divisible by 4. As the answer would be very large use a modulo of 1,000,000,007 (1e9+7).
Note : Sub-sequences can also start with 0.
We didn’t know that this was a standard geeksforgeeks problem. So we apologize for not doing the ground work properly.
Solution:
For divisibility test by 4 it is enough to check the last two digits. So if we know the number of sub-sequences ending at a particular digit then the task becomes very simple.
Lets say we are currently at a position i in the number, if we want to count the number of sub-sequences ending at i which is divisible by 4 then we have choose the second last digit between 0-9 and check whether the last two digits are divisible by 4. If they are divisible then we add the number of sub-sequences ending at second last digit to the answer.
The one case that some people missed during the contest is that they forgot to handle the single digit case, which was also required to get the answer.
Time Complexity : O(No. of Digits)