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?