Jun
28
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?