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:
- Convierte el número binario a base 4.
- Los números en base 4 contienen solo 0, 1, 2, 3 como sus dígitos.
- 5 en base 4 es equivalente a 11.
- 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?
- Compruebe si la longitud de la string binaria es par o impar.
- Si es impar, agregue ‘0’ al comienzo de la string.
- Ahora, atraviesa la cuerda de izquierda a derecha.
- Uno, extraiga substrings de tamaño 2 y agregue su decimal equivalente a la string resultante.
Implementación:
C++
// 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
//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)); } }
Python 3
# 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#
// 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
Javascript
<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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA