Number of subsequences in a string divisible by n - GeeksforGeeks
Given a string consisting of digits 0-9, count the number of subsequences in it divisible by m.
Given a string consisting of digits 0-9, count the number of subsequences in it divisible by m.
Input : str = "1234", n = 4 Output : 4 The subsequences 4, 12, 24 and 124 are divisible by 4
This problem can be recursively defined. Let remainder of a string with value x be ‘r’ when divided with n. Adding one more character to this string changes its remainder to (r*10 + newdigit) % n. For every new character, we have two choices, either add it in all current subsequences or ignore it. Thus, we have an optimal substructure. Following shows the brute force version of this:
string str = "330"; int n = 6 // idx is value of current index in str // rem is current remainder int count(int idx, int rem) { // If last character reached if (idx == n) return (rem == 0)? 1 : 0; int ans = 0; // we exclude it, thus remainder // remains the same ans += count(idx+1, rem); // we include it and thus new remainder ans += count(idx+1, (rem*10 + str[idx]-'0')%n); return ans; }
The above recursive solution has overlapping subproblems as shown in below recursion tree.
input string = "330" (0,0) ===> at 0th index with 0 remainder (exclude 0th / \ (include 0th character) character) / \ (1,0) (1,3) ======> at index 1 with 3 as (E)/ \(I) /(E) the current remainder (2,0) (2,3) (2,3) |-------| These two subproblems overlap
Time Complexity : O(len * n)
Auxiliary Space : O(len * n)
Auxiliary Space : O(len * n)