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

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

Ejemplos: 

Entrada: str = «101» 
Salida: 2 
«0» y «10» son las únicas substrings 
que son divisibles por 2.

Entrada: str = “10010” 
Salida: 10 

Enfoque ingenuo: un enfoque ingenuo será generar todas las substrings posibles y comprobar si son divisibles por 2. La complejidad de tiempo para esto será O(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 substrings que terminan en 0 . Entonces, para cada índice i tal que str[i] = ‘0’ , encuentra el número de substrings que terminan en i . Este valor es igual a (i + 1) (indexación basada en 0). Por lo tanto, la respuesta final será igual a la suma de (i + 1) para todos los 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 substrings
int countSubStr(string str, int len)
{
    // To store the final answer
    int ans = 0;
 
    // Loop to find the answer
    for (int i = 0; i < len; i++) {
 
        // Condition to update the answer
        if (str[i] == '0')
            ans += (i + 1);
    }
 
    return ans;
}
 
// Driver code
int main()
{
    string str = "10010";
    int len = str.length();
 
    cout << countSubStr(str, len);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
    // Function to return the count
    // of the required substrings
    static int countSubStr(String str, int len)
    {
        // To store the final answer
        int ans = 0;
     
        // Loop to find the answer
        for (int i = 0; i < len; i++)
        {
     
            // Condition to update the answer
            if (str.charAt(i) == '0')
                ans += (i + 1);
        }
        return ans;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        String str = "10010";
        int len = str.length();
     
        System.out.println(countSubStr(str, len));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to return the count
# of the required substrings
def countSubStr(strr, lenn):
     
    # To store the final answer
    ans = 0
 
    # Loop to find the answer
    for i in range(lenn):
 
        # Condition to update the answer
        if (strr[i] == '0'):
            ans += (i + 1)
 
    return ans
 
# Driver code
strr = "10010"
lenn = len(strr)
 
print(countSubStr(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 substrings
    static int countSubStr(string str, int len)
    {
        // To store the final answer
        int ans = 0;
     
        // Loop to find the answer
        for (int i = 0; i < len; i++)
        {
     
            // Condition to update the answer
            if (str[i] == '0')
                ans += (i + 1);
        }
        return ans;
    }
     
    // Driver code
    public static void Main ()
    {
        string str = "10010";
        int len = str.Length;
     
        Console.WriteLine(countSubStr(str, len));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript implementation of the approach
 
// Function to return the count
// of the required substrings
function countSubStr(str, len)
{
    // To store the final answer
    var ans = 0;
 
    // Loop to find the answer
    for (var i = 0; i < len; i++) {
 
        // Condition to update the answer
        if (str[i] == '0')
            ans += (i + 1);
    }
 
    return ans;
}
 
// Driver code
var str = "10010";
var len = str.length;
document.write( countSubStr(str, len));
 
</script>

10

Complejidad de tiempo: O(N), N = Longitud de string

Espacio Auxiliar: O(1)