Number of sub-strings in a given binary string divisible by 2
Given binary string str of length N, the task is to find the count of substrings of str which are divisible by 2. Leading zeros in a substring are allowed.
Examples:
Input: str = “101”
Output: 2
“0” and “10” are the only substrings
which are divisible by 2.Input: str = “10010”
Output: 10
Naive approach: A naive approach will be to generate all possible substrings and check if they are divisible by 2. The time complexity for this will be O(N3).
Efficient approach: It can be observed that any binary number is divisible by 2 only if it ends with a 0. Now, the task is to just count the number of substrings ending with 0. So, for every index i such that str[i] = ‘0’, find the number of substrings ending at i. This value is equal to (i + 1) (0-based indexing). Thus, the final answer will be equal to the summation of (i + 1) for all i such that str[i] = ‘0’.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count // of the required substrings int countSubStr(string str, int len) { // To store the final answer int ans = 0; // Loop to find the answer for ( int i = 0; i < len; i++) { // Condition to update the answer if (str[i] == '0' ) ans += (i + 1); } return ans; } // Driver code int main() { string str = "10010" ; int len = str.length(); cout << countSubStr(str, len); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the count // of the required substrings static int countSubStr(String str, int len) { // To store the final answer int ans = 0 ; // Loop to find the answer for ( int i = 0 ; i < len; i++) { // Condition to update the answer if (str.charAt(i) == '0' ) ans += (i + 1 ); } return ans; } // Driver code public static void main (String[] args) { String str = "10010" ; int len = str.length(); System.out.println(countSubStr(str, len)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to return the count # of the required substrings def countSubStr(strr, lenn): # To store the final answer ans = 0 # Loop to find the answer for i in range (lenn): # Condition to update the answer if (strr[i] = = '0' ): ans + = (i + 1 ) return ans # Driver code strr = "10010" lenn = len (strr) print (countSubStr(strr, lenn)) # This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System; class GFG { // Function to return the count // of the required substrings static int countSubStr( string str, int len) { // To store the final answer int ans = 0; // Loop to find the answer for ( int i = 0; i < len; i++) { // Condition to update the answer if (str[i] == '0' ) ans += (i + 1); } return ans; } // Driver code public static void Main () { string str = "10010" ; int len = str.Length; Console.WriteLine(countSubStr(str, len)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the approach // Function to return the count // of the required substrings function countSubStr(str, len) { // To store the final answer var ans = 0; // Loop to find the answer for ( var i = 0; i < len; i++) { // Condition to update the answer if (str[i] == '0' ) ans += (i + 1); } return ans; } // Driver code var str = "10010" ; var len = str.length; document.write( countSubStr(str, len)); </script> |
10
Time Complexity: O(N), N = String length
Auxiliary Space: O(1)
Contact Us