La representación decimal de una string binaria dada es divisible por 5 o no

El problema es verificar si la representación decimal del número binario dado es divisible por 5 o no. Tenga cuidado, el número podría ser muy grande y no encajar incluso en long long int. El enfoque debe ser tal que haya cero o un número mínimo de operaciones de multiplicación y división. No hay 0 a la izquierda en la entrada. 

Ejemplos:

Input : 1010
Output : YES
(1010)2 = (10)10,
and 10 is divisible by 5.

Input : 10000101001
Output : YES

Acercarse: 

Los siguientes pasos son:

1. Convierte el número binario a base 4.
2. Los números en base 4 contienen solo 0, 1, 2, 3 como sus dígitos.
3. 5 en base 4 es equivalente a 11.
4. Ahora aplica la regla de divisibilidad por 11 donde sumas todos los dígitos en lugares impares y sumas todos los dígitos en lugares pares y luego restas uno del otro. Si el resultado es divisible por 11 (que recuerda que es 5), entonces el número binario es divisible por 5.

¿Cómo convertir un número binario a representación base 4?

1. Compruebe si la longitud de la string binaria es par o impar.
2. Si es impar, agregue ‘0’ al comienzo de la string.
3. Ahora, atraviesa la cuerda de izquierda a derecha.
4. Uno, extraiga substrings de tamaño 2 y agregue su decimal equivalente a la string resultante.

Implementación:

// C++ implementation to check whether decimal representation
// of given binary number is divisible by 5 or not
#include <bits/stdc++.h>
 
using namespace std;
 
// function to return equivalent base 4 number
// of the given binary number
int equivalentBase4(string bin)
{
    if (bin.compare("00") == 0)
        return 0;
    if (bin.compare("01") == 0)
        return 1;
    if (bin.compare("10") == 0)
        return 2;
    return 3;
}
 
// function to check whether the given binary
// number is divisible by 5 or not
string isDivisibleBy5(string bin)
{
    int l = bin.size();
     
    if (l % 2 != 0)
    // add '0' in the beginning to make
    // length an even number
        bin = '0' + bin;
     
    // to store sum of digits at odd and
    // even places respectively
    int odd_sum, even_sum = 0;
     
    // variable check for odd place and
    // even place digit
    int isOddDigit = 1;
    for (int i = 0; i<bin.size(); i+= 2)
    {
        // if digit of base 4 is at odd place, then
        // add it to odd_sum
        if (isOddDigit)
            odd_sum += equivalentBase4(bin.substr(i, 2));
        // else digit of base 4 is at even place,
        // add it to even_sum
        else
            even_sum += equivalentBase4(bin.substr(i, 2));
         
        isOddDigit ^= 1;
    }
     
    // if this diff is divisible by 11(which is 5 in decimal)
    // then, the binary number is divisible by 5
    if (abs(odd_sum - even_sum) % 5 == 0)
        return "Yes";
     
    // else not divisible by 5
    return "No";
             
}
 
// Driver program to test above
int main()
{
    string bin = "10000101001";
    cout << isDivisibleBy5(bin);
    return 0;
}

//Java implementation to check whether decimal representation
//of given binary number is divisible by 5 or not
 
class GFG
{
    // Method to return equivalent base 4 number
    // of the given binary number
    static int equivalentBase4(String bin)
    {
        if (bin.compareTo("00") == 0)
            return 0;
        if (bin.compareTo("01") == 0)
            return 1;
        if (bin.compareTo("10") == 0)
            return 2;
        return 3;
    }
     
    // Method to check whether the given binary
    // number is divisible by 5 or not
    static String isDivisibleBy5(String bin)
    {
        int l = bin.length();
         
        if (l % 2 != 0)
        // add '0' in the beginning to make
        // length an even number
            bin = '0' + bin;
         
        // to store sum of digits at odd and
        // even places respectively
        int odd_sum=0, even_sum = 0;
         
        // variable check for odd place and
        // even place digit
        int isOddDigit = 1;
        for (int i = 0; i<bin.length(); i+= 2)
        {
            // if digit of base 4 is at odd place, then
            // add it to odd_sum
            if (isOddDigit != 0)
                odd_sum += equivalentBase4(bin.substring(i, i+2));
            // else digit of base 4 is at even place,
            // add it to even_sum
            else
                even_sum += equivalentBase4(bin.substring(i, i+2));
             
            isOddDigit ^= 1;
        }
         
        // if this diff is divisible by 11(which is 5 in decimal)
        // then, the binary number is divisible by 5
        if (Math.abs(odd_sum - even_sum) % 5 == 0)
            return "Yes";
         
        // else not divisible by 5
        return "No";
                 
    }
     
    public static void main (String[] args)
    {
        String bin = "10000101001";
        System.out.println(isDivisibleBy5(bin));
    }
}

# Python3 implementation to check whether
# decimal representation of given binary
# number is divisible by 5 or not
 
# function to return equivalent base 4
# number of the given binary number
def equivalentBase4(bin):
    if(bin == "00"):
        return 0
    if(bin == "01"):
        return 1
    if(bin == "10"):
        return 2
    if(bin == "11"):
        return 3
     
# function to check whether the given
# binary number is divisible by 5 or not    
def isDivisibleBy5(bin):
    l = len(bin)
    if((l % 2) == 1):
         
    # add '0' in the beginning to
    # make length an even number    
        bin = '0' + bin
         
    # to store sum of digits at odd
    # and even places respectively
    odd_sum = 0
    even_sum = 0
    isOddDigit = 1
    for i in range(0, len(bin), 2):
         
        # if digit of base 4 is at odd place,
        # then add it to odd_sum
        if(isOddDigit):
            odd_sum += equivalentBase4(bin[i:i + 2])
             
        # else digit of base 4 is at
        # even place, add it to even_sum    
        else:
            even_sum += equivalentBase4(bin[i:i + 2])
             
        isOddDigit = isOddDigit ^ 1
 
    # if this diff is divisible by 11(which is
    # 5 in decimal) then, the binary number is
    # divisible by 5
    if(abs(odd_sum - even_sum) % 5 == 0):
        return "Yes"
    else:
        return "No"
 
# Driver Code
if __name__=="__main__":
    bin = "10000101001"
    print(isDivisibleBy5(bin))
 
# This code is contributed
# by Sairahul Jella

// C# implementation to check whether
// decimal representation of given
// binary number is divisible by 5 or not
using System;
 
class GFG
{
// Method to return equivalent base
// 4 number of the given binary number
public static int equivalentBase4(string bin)
{
    if (bin.CompareTo("00") == 0)
    {
        return 0;
    }
    if (bin.CompareTo("01") == 0)
    {
        return 1;
    }
    if (bin.CompareTo("10") == 0)
    {
        return 2;
    }
    return 3;
}
 
// Method to check whether the
// given binary number is divisible
// by 5 or not
public static string isDivisibleBy5(string bin)
{
    int l = bin.Length;
 
    if (l % 2 != 0)
    {
        // add '0' in the beginning to
        // make length an even number
        bin = '0' + bin;
    }
 
    // to store sum of digits at odd
    // and even places respectively
    int odd_sum = 0, even_sum = 0;
 
    // variable check for odd place
    // and even place digit
    int isOddDigit = 1;
    for (int i = 0; i < bin.Length; i += 2)
    {
        // if digit of base 4 is at odd
        // place, then add it to odd_sum
        if (isOddDigit != 0)
        {
            odd_sum += equivalentBase4(
                             bin.Substring(i, 2));
        }
         
        // else digit of base 4 is at even 
        // place, add it to even_sum
        else
        {
            even_sum += equivalentBase4(
                              bin.Substring(i, 2));
        }
 
        isOddDigit ^= 1;
    }
 
    // if this diff is divisible by
    // 11(which is 5 in decimal) then,
    // the binary number is divisible by 5
    if (Math.Abs(odd_sum - even_sum) % 5 == 0)
    {
        return "YES";
    }
 
    // else not divisible by 5
    return "NO";
 
}
 
// Driver Code
public static void Main(string[] args)
{
    string bin = "10000101001";
    Console.WriteLine(isDivisibleBy5(bin));
}
}
 
// This code is contributed by Shrikant13

<script>
 
// Javascript implementation to check whether
// decimal representation of given binary
// number is divisible by 5 or not
 
// function to return equivalent base 4
// number of the given binary number
function equivalentBase4(bin){
    if(bin == "00")
        return 0
    if(bin == "01")
        return 1
    if(bin == "10")
        return 2
    if(bin == "11")
        return 3
}
     
// function to check whether the given
// binary number is divisible by 5 or not   
function isDivisibleBy5(bin){
    let l = bin.length
    if((l % 2) == 1){
         
    // add '0' in the beginning to
    // make length an even number   
        bin = '0' + bin
    }
         
    // to store sum of digits at odd
    // and even places respectively
    let odd_sum = 0
    let even_sum = 0
    let isOddDigit = 1
    for(let i=0;i<bin.length;i+=2){
         
        // if digit of base 4 is at odd place,
        // then add it to odd_sum
        if(isOddDigit)
            odd_sum += equivalentBase4(bin.substring(i,i + 2))
             
        // else digit of base 4 is at
        // even place, add it to even_sum   
        else
            even_sum += equivalentBase4(bin.substring(i,i + 2))
             
        isOddDigit = isOddDigit ^ 1
    }
 
    // if this diff is divisible by 11(which is
    // 5 in decimal) then, the binary number is
    // divisible by 5
    if(Math.abs(odd_sum - even_sum) % 5 == 0)
        return "Yes"
    else
        return "No"
}
 
// Driver Code
 
let    bin = "10000101001"
document.writeln(isDivisibleBy5(bin))
 
// This code is contributed by shinjanpatra
 
</script>

No

Complejidad temporal: O(n), donde n es el número de dígitos del número binario. 
Espacio Auxiliar: O(1)

Este artículo es una contribución de Aarti_Rathi y Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.