Number of subsequences in a given binary string divisible by 2

0 0 3 minutes read

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(2^N * 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 2ⁱ (0-based indexing). Thus, the final answer will be equal to the summation of 2ⁱ 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 subsequences
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
int main()
{
    string str = "10010";
    int len = str.length();
 
    cout << countSubSeq(str, len);
 
    return 0;
}

Java

// Java implementation of the approach
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.charAt(i) == '0')
            ans += mul;
             
        // updating multiplier
        mul *= 2;
    }
    return ans;
}
 
// Driver code
public 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 subsequences
def 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 code
strr = "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 subsequences
function 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 code
var str = "10010";
var len = str.length;
document.write( countSubSeq(str, len));
 
</script>

Output:

Time Complexity: O(len), where len is the size of the given string
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!