Dada una string binaria y un número k , la tarea es verificar si la string binaria es divisible por 2 k o no.
Ejemplos:
Input : 11000 k = 2 Output : Yes Explanation : (11000)2 = (24)10 24 is evenly divisible by 2k i.e. 4. Input : 10101 k = 3 Output : No Explanation : (10101)2 = (21)10 21 is not evenly divisible by 2k i.e. 8.
Enfoque ingenuo: calcule la string binaria en decimal y luego simplemente verifique si es divisible por 2 k . Sin embargo, este enfoque no es factible para las strings binarias largas, ya que la complejidad del tiempo será alta para calcular el número decimal de la string binaria y luego dividirlo por 2 k .
Enfoque eficiente: en la string binaria, verifique los últimos k bits. Si todos los últimos k bits son 0, entonces el número binario es divisible por 2 k ; de lo contrario, no es divisible por igual. La complejidad del tiempo usando este enfoque es O(k).
A continuación se muestra la implementación del enfoque.
C++
// C++ implementation to check whether
// given binary number is evenly
// divisible by 2^k or not
#include <bits/stdc++.h>
using namespace std;
// function to check whether
// given binary number is
// evenly divisible by 2^k or not
bool isDivisible(char str[], int k)
{
int n = strlen(str);
int c = 0;
// count of number of 0 from last
for (int i = 0; i < k; i++)
if (str[n - i - 1] == '0')
c++;
// if count = k, number is evenly
// divisible, so returns true else
// false
return (c == k);
}
// Driver program to test above
int main()
{
// first example
char str1[] = "10101100";
int k = 2;
if (isDivisible(str1, k))
cout << "Yes" << endl;
else
cout << "No"
<< "\n";
// Second example
char str2[] = "111010100";
k = 2;
if (isDivisible(str2, k))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java implementation to check whether
// given binary number is evenly
// divisible by 2^k or not
class GFG {
// function to check whether
// given binary number is
// evenly divisible by 2^k or not
static boolean isDivisible(String str, int k)
{
int n = str.length();
int c = 0;
// count of number of 0 from last
for (int i = 0; i < k; i++)
if (str.charAt(n - i - 1) == '0')
c++;
// if count = k, number is evenly
// divisible, so returns true else
// false
return (c == k);
}
// Driver program to test above
public static void main(String args[])
{
// first example
String str1 = "10101100";
int k = 2;
if (isDivisible(str1, k) == true)
System.out.println("Yes");
else
System.out.println("No");
// Second example
String str2 = "111010100";
k = 2;
if (isDivisible(str2, k) == true)
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by JaideepPyne.
Python3
# Python 3 implementation to check
# whether given binary number is
# evenly divisible by 2^k or not
# function to check whether
# given binary number is
# evenly divisible by 2^k or not
def isDivisible(str, k):
n = len(str)
c = 0
# count of number of 0 from last
for i in range(0, k):
if (str[n - i - 1] == '0'):
c += 1
# if count = k, number is evenly
# divisible, so returns true else
# false
return (c == k)
# Driver program to test above
# first example
str1 = "10101100"
k = 2
if (isDivisible(str1, k)):
print("Yes")
else:
print("No")
# Second example
str2 = "111010100"
k = 2
if (isDivisible(str2, k)):
print("Yes")
else:
print("No")
# This code is contributed by Smitha
C#
// C# implementation to check whether
// given binary number is evenly
// divisible by 2^k or not
using System;
class GFG {
// function to check whether
// given binary number is
// evenly divisible by 2^k or not
static bool isDivisible(String str, int k)
{
int n = str.Length;
int c = 0;
// count of number of 0 from last
for (int i = 0; i < k; i++)
if (str[n - i - 1] == '0')
c++;
// if count = k, number is evenly
// divisible, so returns true else
// false
return (c == k);
}
// Driver program to test above
public static void Main()
{
// first example
String str1 = "10101100";
int k = 2;
if (isDivisible(str1, k) == true)
Console.Write("Yes\n");
else
Console.Write("No");
// Second example
String str2 = "111010100";
k = 2;
if (isDivisible(str2, k) == true)
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by Smitha.
PHP
<?php
// PHP implementation to check whether
// given binary number is evenly
// function to check whether
// given binary number is
// evenly divisible by 2^k or not
function isDivisible($str, $k)
{
$n = strlen($str);
$c = 0;
// count of number
// of 0 from last
for ($i = 0; $i < $k; $i++)
if ($str[$n - $i - 1] == '0')
$c++;
// if count = k,
// number is evenly
// divisible, so
// returns true else
// false
return ($c == $k);
}
// Driver Code
// first example
$str1 = "10101100";
$k = 2;
if (isDivisible($str1, $k))
echo "Yes", "\n";
else
echo "No", "\n";
// Second example
$str2= "111010100";
$k = 2;
if (isDivisible($str2, $k))
echo "Yes", "\n";
else
echo "No", "\n";
// This code is contributed by Ajit
?>
Javascript
<script>
// Javascript implementation to check whether
// given binary number is evenly
// divisible by 2^k or not
// Function to check whether
// given binary number is
// evenly divisible by 2^k or not
function isDivisible(str, k)
{
let n = str.length;
let c = 0;
// Count of number of 0 from last
for(let i = 0; i < k; i++)
if (str[n - i - 1] == '0')
c++;
// If count = k, number is evenly
// divisible, so returns true else
// false
return (c == k);
}
// Driver code
// First example
let str1 = "10101100";
let k = 2;
if (isDivisible(str1, k) == true)
document.write("Yes" + "</br>");
else
document.write("No");
// Second example
let str2 = "111010100";
k = 2;
if (isDivisible(str2, k) == true)
document.write("Yes");
else
document.write("No");
// This code is contributed by rameshtravel07
</script>
Producción:
Yes Yes
Complejidad de tiempo: O(k)
Espacio Auxiliar: O(1)