Número de formas de dividir un número binario de modo que cada parte sea divisible por 2

Dada una string binaria S , la tarea es encontrar el número de formas de dividirla en partes de modo que cada parte sea divisible por 2 .

Ejemplos: 

Entrada: S = “100” 
Salida: 2 
Hay dos formas de dividir la string: 
{“10”, “0”} y {“100”}
Entrada: S = “110” 
Salida: 1 

Enfoque: una observación es que la string solo se puede dividir después de un 0 . Por lo tanto, cuente el número de ceros en la string. Llamemos a este conteo c_zero . Asumiendo el caso cuando la string es par, por cada 0 excepto el que está más a la derecha, hay dos opciones, es decir, cortar la string después de ese cero o no hacerlo. Por lo tanto, la respuesta final se convierte en 2 ^{(c_zero – 1)} para strings pares. 
El caso en el que la string no se puede dividir es el caso cuando termina en 1 . Por lo tanto, para las strings impares, la respuesta siempre será cero, ya que la última parte dividida siempre será impar.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define maxN 20
#define maxM 64
 
// Function to return the required count
int cntSplits(string s)
{
    // If the splitting is not possible
    if (s[s.size() - 1] == '1')
        return 0;
 
    // To store the count of zeroes
    int c_zero = 0;
 
    // Counting the number of zeroes
    for (int i = 0; i < s.size(); i++)
        c_zero += (s[i] == '0');
 
    // Return the final answer
    return (int)pow(2, c_zero - 1);
}
 
// Driver code
int main()
{
    string s = "10010";
 
    cout << cntSplits(s);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
static int maxN = 20;
static int maxM = 64;
 
// Function to return the required count
static int cntSplits(String s)
{
    // If the splitting is not possible
    if (s.charAt(s.length() - 1) == '1')
        return 0;
 
    // To store the count of zeroes
    int c_zero = 0;
 
    // Counting the number of zeroes
    for (int i = 0; i < s.length(); i++)
        c_zero += (s.charAt(i) == '0') ? 1 : 0;
 
    // Return the final answer
    return (int)Math.pow(2, c_zero - 1);
}
 
// Driver code
public static void main(String []args)
{
    String s = "10010";
 
    System.out.println(cntSplits(s));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
 
# Function to return the required count
def cntSplits(s) :
 
    # If the splitting is not possible
    if (s[len(s) - 1] == '1') :
        return 0;
 
    # To store the count of zeroes
    c_zero = 0;
 
    # Counting the number of zeroes
    for i in range(len(s)) :
        c_zero += (s[i] == '0');
 
    # Return the final answer
    return int(pow(2, c_zero - 1));
 
# Driver code
if __name__ == "__main__" :
 
    s = "10010";
 
    print(cntSplits(s));
     
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
                     
class GFG
{
 
static int maxN = 20;
static int maxM = 64;
 
// Function to return the required count
static int cntSplits(String s)
{
    // If the splitting is not possible
    if (s[s.Length - 1] == '1')
        return 0;
 
    // To store the count of zeroes
    int c_zero = 0;
 
    // Counting the number of zeroes
    for (int i = 0; i < s.Length; i++)
        c_zero += (s[i] == '0') ? 1 : 0;
 
    // Return the final answer
    return (int)Math.Pow(2, c_zero - 1);
}
 
// Driver code
public static void Main(String []args)
{
    String s = "10010";
 
    Console.WriteLine(cntSplits(s));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
var maxN = 20;
var maxM = 64;
 
// Function to return the required count
function cntSplits(s)
{
    // If the splitting is not possible
    if (s[s.length - 1] == '1')
        return 0;
 
    // To store the count of zeroes
    var c_zero = 0;
 
    // Counting the number of zeroes
    for (var i = 0; i < s.length; i++)
        c_zero += (s[i] == '0');
 
    // Return the final answer
    return Math.pow(2, c_zero - 1);
}
 
// Driver code
var s = "10010";
document.write( cntSplits(s));
 
</script>

4

Complejidad temporal: O(N)
Espacio auxiliar: O(1)