El problema es verificar si la representación decimal del número binario dado es divisible por 20 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 : 101000 Output : Yes (10100)2 = (40)10 and 40 is divisible by 20. Input : 110001110011100 Output : Yes
Enfoque: Los siguientes son los pasos:
- Deje que la string binaria sea bin[] .
- Deje que la longitud de bin[] sea n .
- Si bin[n-1] == ‘1’, entonces es un número impar y, por lo tanto, no es divisible por 20.
- De lo contrario, compruebe si bin[0..n-2] es divisible por 10. Consulte esta publicación.
C++
// C++ implementation to check whether
// decimal representation of given binary
// number is divisible by 20 or not
#include <bits/stdc++.h>
using namespace std;
// function to check whether decimal
// representation of given binary number
// is divisible by 10 or not
bool isDivisibleBy10(char bin[], int n)
{
// if last digit is '1', then
// number is not divisible by 10
if (bin[n - 1] == '1')
return false;
// to accumulate the sum of last digits
// in perfect powers of 2
int sum = 0;
// traverse from the 2nd last up
// to 1st digit in 'bin'
for (int i = n - 2; i >= 0; i--) {
// if digit in '1'
if (bin[i] == '1') {
// calculate digit's position from
// the right
int posFromRight = n - i - 1;
// according to the digit's position,
// obtain the last digit of the
// applicable perfect power of 2
if (posFromRight % 4 == 1)
sum = sum + 2;
else if (posFromRight % 4 == 2)
sum = sum + 4;
else if (posFromRight % 4 == 3)
sum = sum + 8;
else if (posFromRight % 4 == 0)
sum = sum + 6;
}
}
// if last digit is 0, then
// divisible by 10
if (sum % 10 == 0)
return true;
// not divisible by 10
return false;
}
// function to check whether decimal
// representation of given binary number
// is divisible by 20 or not
bool isDivisibleBy20(char bin[], int n)
{
// if 'bin' is an odd number
if (bin[n - 1] == '1')
return false;
// check if bin(0..n-2) is divisible
// by 10 or not
return isDivisibleBy10(bin, n - 1);
}
// Driver program to test above
int main()
{
char bin[] = "101000";
int n = sizeof(bin) / sizeof(bin[0]);
if (isDivisibleBy20(bin, n - 1))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation to check whether
// decimal representation of given binary
// number is divisible by 20 or not
import java.io.*;
class GFG {
// function to check whether decimal
// representation of given binary number
// is divisible by 10 or not
static boolean isDivisibleBy10(char bin[], int n)
{
// if last digit is '1', then
// number is not divisible by 10
if (bin[n - 1] == '1')
return false;
// to accumulate the sum of last
// digits in perfect powers of 2
int sum = 0;
// traverse from the 2nd last up
// to 1st digit in 'bin'
for (int i = n - 2; i >= 0; i--) {
// if digit in '1'
if (bin[i] == '1') {
// calculate digit's position from
// the right
int posFromRight = n - i - 1;
// according to the digit's position,
// obtain the last digit of the
// applicable perfect power of 2
if (posFromRight % 4 == 1)
sum = sum + 2;
else if (posFromRight % 4 == 2)
sum = sum + 4;
else if (posFromRight % 4 == 3)
sum = sum + 8;
else if (posFromRight % 4 == 0)
sum = sum + 6;
}
}
// if last digit is 0, then
// divisible by 10
if (sum % 10 == 0)
return true;
// not divisible by 10
return false;
}
// function to check whether decimal
// representation of given binary number
// is divisible by 20 or not
static boolean isDivisibleBy20(char bin[], int n)
{
// if 'bin' is an odd number
if (bin[n - 1] == '1')
return false;
// check if bin(0..n-2) is divisible
// by 10 or not
return isDivisibleBy10(bin, n - 1);
}
// Driver program to test above
public static void main(String args[])
{
char bin[] = "101000".toCharArray();
int n = bin.length;
if (isDivisibleBy20(bin, n - 1))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed
// by Nikita Tiwari.
Python3
# Python 3 implementation to check whether
# decimal representation of given binary
# number is divisible by 20 or not
# function to check whether decimal
# representation of given binary number
# is divisible by 10 or not
def isDivisibleBy10(bin, n):
# if last digit is '1', then
# number is not divisible by 10
if (bin[n - 1] == '1'):
return False
# to accumulate the sum of last digits
# in perfect powers of 2
sum = 0
# traverse from the 2nd last up
# to 1st digit in 'bin'
for i in range(n - 2, -1, -1):
# if digit in '1'
if (bin[i] == '1') :
# calculate digit's position from
# the right
posFromRight = n - i - 1
# according to the digit's position,
# obtain the last digit of the
# applicable perfect power of 2
if (posFromRight % 4 == 1):
sum = sum + 2
elif (posFromRight % 4 == 2):
sum = sum + 4
elif (posFromRight % 4 == 3):
sum = sum + 8
elif (posFromRight % 4 == 0):
sum = sum + 6
# if last digit is 0, then
# divisible by 10
if (sum % 10 == 0):
return True
# not divisible by 10
return False
# function to check whether decimal
# representation of given binary number
# is divisible by 20 or not
def isDivisibleBy20(bin, n):
# if 'bin' is an odd number
if (bin[n - 1] == '1'):
return false
# check if bin(0..n-2) is divisible
# by 10 or not
return isDivisibleBy10(bin, n - 1)
# Driver program to test above
bin = ['1','0','1','0','0','0']
n = len(bin)
if (isDivisibleBy20(bin, n - 1)):
print("Yes")
else:
print("No")
# This code is contributed by Smitha Dinesh Semwal
C#
// C# implementation to check whether
// decimal representation of given binary
// number is divisible by 20 or not
using System;
class GFG {
// function to check whether decimal
// representation of given binary number
// is divisible by 10 or not
static bool isDivisibleBy10(string bin, int n)
{
// if last digit is '1', then
// number is not divisible by 10
if (bin[n - 1] == '1')
return false;
// to accumulate the sum of last
// digits in perfect powers of 2
int sum = 0;
// traverse from the 2nd last up
// to 1st digit in 'bin'
for (int i = n - 2; i >= 0; i--) {
// if digit in '1'
if (bin[i] == '1') {
// calculate digit's position from
// the right
int posFromRight = n - i - 1;
// according to the digit's position,
// obtain the last digit of the
// applicable perfect power of 2
if (posFromRight % 4 == 1)
sum = sum + 2;
else if (posFromRight % 4 == 2)
sum = sum + 4;
else if (posFromRight % 4 == 3)
sum = sum + 8;
else if (posFromRight % 4 == 0)
sum = sum + 6;
}
}
// if last digit is 0, then
// divisible by 10
if (sum % 10 == 0)
return true;
// not divisible by 10
return false;
}
// function to check whether decimal
// representation of given binary number
// is divisible by 20 or not
static bool isDivisibleBy20(string bin, int n)
{
// if 'bin' is an odd number
if (bin[n - 1] == '1')
return false;
// check if bin(0..n-2) is divisible
// by 10 or not
return isDivisibleBy10(bin, n - 1);
}
// Driver program to test above
public static void Main()
{
string bin = "101000";
int n = bin.Length;
if (isDivisibleBy20(bin, n - 1))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed
// by vt_m.
PHP
<?php
// PHP implementation to check whether
// decimal representation of given binary
// number is divisible by 20 or not
// function to check whether decimal
// representation of given binary number
// is divisible by 10 or not
function isDivisibleBy10($bin, $n)
{
// if last digit is '1', then
// number is not divisible by 10
if ($bin[$n - 1] == '1')
return false;
// to accumulate the sum of last
// digits in perfect powers of 2
$sum = 0;
// traverse from the 2nd last up
// to 1st digit in 'bin'
for ($i = $n - 2; $i >= 0; $i--)
{
// if digit in '1'
if ($bin[$i] == '1')
{
// calculate digit's position
// from the right
$posFromRight = $n - $i - 1;
// according to the digit's position,
// obtain the last digit of the
// applicable perfect power of 2
if ($posFromRight % 4 == 1)
$sum = $sum + 2;
else if ($posFromRight % 4 == 2)
$sum = $sum + 4;
else if ($posFromRight % 4 == 3)
$sum = $sum + 8;
else if ($posFromRight % 4 == 0)
$sum = $sum + 6;
}
}
// if last digit is 0, then
// divisible by 10
if ($sum % 10 == 0)
return true;
// not divisible by 10
return false;
}
// function to check whether decimal
// representation of given binary number
// is divisible by 20 or not
function isDivisibleBy20($bin, $n)
{
// if 'bin' is an odd number
if ($bin[$n - 1] == '1')
return false;
// check if bin(0..n-2) is divisible
// by 10 or not
return isDivisibleBy10($bin, $n - 1);
}
// Driver code
$bin= "101000";
$n = strlen($bin);
if (isDivisibleBy20($bin, $n - 1))
echo "Yes";
else
echo "No";
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript implementation to check whether
// decimal representation of given binary
// number is divisible by 20 or not
// function to check whether decimal
// representation of given binary number
// is divisible by 10 or not
function isDivisibleBy10(bin, n)
{
// if last digit is '1', then
// number is not divisible by 10
if (bin[n - 1] == '1')
return false;
// to accumulate the sum of last digits
// in perfect powers of 2
var sum = 0;
// traverse from the 2nd last up
// to 1st digit in 'bin'
for (var i = n - 2; i >= 0; i--) {
// if digit in '1'
if (bin[i] == '1') {
// calculate digit's position from
// the right
var posFromRight = n - i - 1;
// according to the digit's position,
// obtain the last digit of the
// applicable perfect power of 2
if (posFromRight % 4 == 1)
sum = sum + 2;
else if (posFromRight % 4 == 2)
sum = sum + 4;
else if (posFromRight % 4 == 3)
sum = sum + 8;
else if (posFromRight % 4 == 0)
sum = sum + 6;
}
}
// if last digit is 0, then
// divisible by 10
if (sum % 10 == 0)
return true;
// not divisible by 10
return false;
}
// function to check whether decimal
// representation of given binary number
// is divisible by 20 or not
function isDivisibleBy20(bin, n)
{
// if 'bin' is an odd number
if (bin[n - 1] == '1')
return false;
// check if bin(0..n-2) is divisible
// by 10 or not
return isDivisibleBy10(bin, n - 1);
}
// Driver program to test above
var bin = "101000";
var n = bin.length;
if (isDivisibleBy20(bin, n - 1))
document.write( "Yes");
else
document.write( "No");
</script>
Producción :
Yes
Complejidad temporal: O(n), donde n es el número de dígitos del número binario.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA