Given a binary string S of length N, the task is to find the number of sub-sequences of non-zero length which are divisible by 3. Leading zeros in the sub-sequences are allowed.
Examples:
Input: S = “1001”
Output: 5
“11”, “1001”, “0”, “0” and “00” are
the only subsequences divisible by 3.
Input: S = “1”
Output: 0
Naive approach: Generate all the possible sub-sequences and check if they are divisible by 3. Time complexity for this will be O((2N) * N).
Better approach: Dynamic programming can be used to solve this problem. Let’s look at the states of the DP.
DP[i][r] will store the number of sub-sequences of the substring S[i…N-1] such that they give a remainder of (3 – r) % 3 when divided by 3.
Let’s write the recurrence relation now.
DP[i][r] = DP[i + 1][(r * 2 + s[i]) % 3] + DP[i + 1][r]
The recurrence is derived because of the two choices below:
- Include the current index i in the sub-sequence. Thus, the r will be updated as r = (r * 2 + s[i]) % 3.
- Don’t include a current index in the sub-sequence.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 100int dp[N][3];bool v[N][3];// Function to return the number of// sub-sequences divisible by 3int findCnt(string& s, int i, int r){ // Base-cases if (i == s.size()) { if (r == 0) return 1; else return 0; } // If the state has been solved // before then return its value if (v[i][r]) return dp[i][r]; // Marking the state as solved v[i][r] = 1; // Recurrence relation dp[i][r] = findCnt(s, i + 1, (r * 2 + (s[i] - '0')) % 3) + findCnt(s, i + 1, r); return dp[i][r];}// Driver codeint main(){ string s = "11"; cout << (findCnt(s, 0, 0) - 1); return 0;} |
Java
// Java implementation of the approach class GFG { static final int N = 100; static int dp[][] = new int[N][3]; static int v[][] = new int[N][3]; // Function to return the number of // sub-sequences divisible by 3 static int findCnt(String s, int i, int r) { // Base-cases if (i == s.length()) { if (r == 0) return 1; else return 0; } // If the state has been solved // before then return its value if (v[i][r] == 1) return dp[i][r]; // Marking the state as solved v[i][r] = 1; // Recurrence relation dp[i][r] = findCnt(s, i + 1, (r * 2 + (s.charAt(i) - '0')) % 3) + findCnt(s, i + 1, r); return dp[i][r]; } // Driver code public static void main (String[] args) { String s = "11"; System.out.print(findCnt(s, 0, 0) - 1); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach import numpy as npN = 100dp = np.zeros((N, 3)); v = np.zeros((N, 3));# Function to return the number of # sub-sequences divisible by 3 def findCnt(s, i, r) : # Base-cases if (i == len(s)) : if (r == 0) : return 1; else : return 0; # If the state has been solved # before then return its value if (v[i][r]) : return dp[i][r]; # Marking the state as solved v[i][r] = 1; # Recurrence relation dp[i][r] = findCnt(s, i + 1, (r * 2 + (ord(s[i]) - ord('0'))) % 3) + \ findCnt(s, i + 1, r); return dp[i][r]; # Driver code if __name__ == "__main__" : s = "11"; print(findCnt(s, 0, 0) - 1); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System;class GFG { static readonly int N = 100; static int [,]dp = new int[N, 3]; static int [,]v = new int[N, 3]; // Function to return the number of // sub-sequences divisible by 3 static int findCnt(String s, int i, int r) { // Base-cases if (i == s.Length) { if (r == 0) return 1; else return 0; } // If the state has been solved // before then return its value if (v[i, r] == 1) return dp[i, r]; // Marking the state as solved v[i, r] = 1; // Recurrence relation dp[i, r] = findCnt(s, i + 1, (r * 2 + (s[i] - '0')) % 3) + findCnt(s, i + 1, r); return dp[i, r]; } // Driver code public static void Main(String[] args) { String s = "11"; Console.Write(findCnt(s, 0, 0) - 1); } }// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approachvar N = 100var dp = Array.from(Array(N), ()=> Array(3));var v = Array.from(Array(N), ()=> Array(3));// Function to return the number of// sub-sequences divisible by 3function findCnt(s, i, r){ // Base-cases if (i == s.length) { if (r == 0) return 1; else return 0; } // If the state has been solved // before then return its value if (v[i][r]) return dp[i][r]; // Marking the state as solved v[i][r] = 1; // Recurrence relation dp[i][r] = findCnt(s, i + 1, (r * 2 + (s[i] - '0')) % 3) + findCnt(s, i + 1, r); return dp[i][r];}// Driver codevar s = "11";document.write( (findCnt(s, 0, 0) - 1));</script> |
1
Time Complexity: O(n)
Auxiliary Space: O(n * 3) ⇒ O(n), where n is the length of the given string.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
