Número máximo de divisiones de un número binario

Dada una string binaria S , la tarea es encontrar el número máximo de partes en las que puede dividirla de modo que cada parte sea divisible por 2 . Si la string no se puede dividir cumpliendo las condiciones dadas, imprima -1 .
Ejemplos: 
 

Entrada: S = “100” 
Salida: 2 
Las divisiones son las siguientes: 
“10” y “0”.
Entrada: S = “110” 
Salida: 1 
 

Enfoque: este problema se puede resolver con avidez, comience desde el extremo izquierdo y haga un corte en un índice j tal que j sea el índice más pequeño para el cual la substring hasta j es divisible por 2 . Ahora, continúa este paso con el resto de la cuerda sobrante. También se sabe que cualquier número binario que termine en 0 es divisible por 2 . Por lo tanto, ponga un corte después de todos y cada uno de los ceros y la respuesta será igual al número de ceros en la string. El único caso en el que la respuesta no es posible es cuando la string dada es impar, es decir, no importa cómo se hagan los cortes en la string, 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;
 
// Function to return the required count
int cntSplits(string s)
{
    // If the splitting is not possible
    if (s[s.size() - 1] == '1')
        return -1;
 
    // To store the final ans
    int ans = 0;
 
    // Counting the number of zeros
    for (int i = 0; i < s.size(); i++)
        ans += (s[i] == '0');
 
    // Return the final answer
    return ans;
}
 
// Driver code
int main()
{
    string s = "10010";
 
    cout << cntSplits(s);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// 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 -1;
 
    // To store the final ans
    int ans = 0;
 
    // Counting the number of zeros
    for (int i = 0; i < s.length(); i++)
        ans += (s.charAt(i) == '0') ? 1 : 0;
 
    // Return the final answer
    return ans;
}
 
// Driver code
public static void main(String []args)
{
    String s = "10010";
 
    System.out.println(cntSplits(s));
}
}
 
// This code is contributed by 29AjayKumar

# 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 -1;
 
    # To store the count of zeroes
    ans = 0;
 
    # Counting the number of zeroes
    for i in range(len(s)) :
        ans += (s[i] == '0');
 
    # Return the final answer
    return ans ;
 
# 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
{
 
// Function to return the required count
static int cntSplits(String s)
{
    // If the splitting is not possible
    if (s[s.Length - 1] == '1')
        return -1;
 
    // To store the final ans
    int ans = 0;
 
    // Counting the number of zeros
    for (int i = 0; i < s.Length; i++)
        ans += (s[i] == '0') ? 1 : 0;
 
    // Return the final answer
    return ans;
}
 
// Driver code
public static void Main(String []args)
{
    String s = "10010";
 
    Console.WriteLine(cntSplits(s));
}
}
 
// This code is contributed by Rajput-Ji

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

3

Complejidad de tiempo: O(|s|)

Espacio Auxiliar: O(1)