Given binary string str of length N, the task is to find the count of subsequences of str which are divisible by 2. Leading zeros in a sub-sequence are allowed.
Examples:
Input: str = “101”
Output: 2
“0” and “10” are the only subsequences
which are divisible by 2.
Input: str = “10010”
Output: 22
Naive approach: A naive approach will be to generate all possible sub-sequences and check if they are divisible by 2. The time complexity for this will be O(2N * N).
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 subsequences ending with 0. So, for every index i such that str[i] = ‘0’, find the number of subsequences ending at i. This value is equal to 2i (0-based indexing). Thus, the final answer will be equal to the summation of 2i 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 subsequencesint countSubSeq(string str, int len){ // To store the final answer int ans = 0; // Multiplier int mul = 1; // Loop to find the answer for (int i = 0; i < len; i++) { // Condition to update the answer if (str[i] == '0') ans += mul; // updating multiplier mul *= 2; } return ans;}// Driver codeint main(){ string str = "10010"; int len = str.length(); cout << countSubSeq(str, len); return 0;} |
Java
// Java implementation of the approachclass GFG{// Function to return the count// of the required subsequencesstatic int countSubSeq(String str, int len){ // To store the final answer int ans = 0; // Multiplier int mul = 1; // Loop to find the answer for (int i = 0; i < len; i++) { // Condition to update the answer if (str.charAt(i) == '0') ans += mul; // updating multiplier mul *= 2; } return ans;}// Driver codepublic static void main(String[] args){ String str = "10010"; int len = str.length(); System.out.print(countSubSeq(str, len));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach# Function to return the count# of the required subsequencesdef countSubSeq(strr, lenn): # To store the final answer ans = 0 # Multiplier mul = 1 # Loop to find the answer for i in range(lenn): # Condition to update the answer if (strr[i] == '0'): ans += mul # updating multiplier mul *= 2 return ans# Driver codestrr = "10010"lenn = len(strr)print(countSubSeq(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 subsequences static int countSubSeq(string str, int len) { // To store the final answer int ans = 0; // Multiplier int mul = 1; // Loop to find the answer for (int i = 0; i < len; i++) { // Condition to update the answer if (str[i] == '0') ans += mul; // updating multiplier mul *= 2; } return ans; } // Driver code static public void Main () { string str = "10010"; int len = str.Length; Console.WriteLine(countSubSeq(str, len)); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript implementation of the approach// Function to return the count// of the required subsequencesfunction countSubSeq(str, len){ // To store the final answer var ans = 0; // Multiplier var mul = 1; // Loop to find the answer for (var i = 0; i < len; i++) { // Condition to update the answer if (str[i] == '0') ans += mul; // updating multiplier mul *= 2; } return ans;}// Driver codevar str = "10010";var len = str.length;document.write( countSubSeq(str, len));</script> |
Output:
22
Time Complexity: O(len), where len is the size of the given string
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
