Número de subsecuencias en una string binaria dada divisible por 2

Dada una string binaria str de longitud N , la tarea es encontrar el recuento de subsecuencias de str que son divisibles por 2 . Se permiten los ceros iniciales en una subsecuencia.

Ejemplos:  

Entrada: str = “101” 
Salida: 2 
“0” y “10” son las únicas subsecuencias 
que son divisibles por 2.
Entrada: str = “10010” 
Salida: 22  

Enfoque ingenuo: un enfoque ingenuo será generar todas las subsecuencias posibles y verificar si son divisibles por 2. La complejidad de tiempo para esto será O (2 ^N * N).

Enfoque eficiente: Se puede observar que cualquier número binario es divisible por 2 solo si termina en 0 . Ahora, la tarea es solo contar el número de subsecuencias que terminan en 0 . Entonces, para cada índice i tal que str[i] = ‘0’ , encuentra el número de subsecuencias que terminan en i . Este valor es igual a 2 ⁱ (indexación basada en 0). Por lo tanto, la respuesta final será igual a la suma de 2 ⁱ para todo i tal que str[i] = ‘0’ .

A continuación se muestra la implementación del enfoque anterior: 

// 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 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 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# 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

<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>

Producción: 

22

Complejidad de tiempo: O(len), donde len es el tamaño de la string dada
Espacio auxiliar: O(1)