Dado un gran número en forma de string str y un número K , la tarea es verificar si el número formado por la string str es divisible por K o no, donde K es una potencia de 2.
Ejemplos:
Entrada: str = “5426987513245621541524288”, num = 64
Salida: Sí
Explicación:
Dado que log 2 (64) = 6, el número formado por los últimos 6 dígitos de la string str es divisible por 64.
Entrada: str = “21346775656413259795656497974113461254”, num = 4
Salida: No
Explicación:
Dado que log 2 (4)=2, el número formado por los últimos 2 dígitos de la string str no es divisible por 4.
Enfoque:
Dado que K es una potencia perfecta de 2 . Deje que K se pueda representar como 2 X . Luego, de acuerdo con la regla de divisibilidad de la potencia perfecta de 2, si el último dígito X del número dado es divisible por K , entonces el número dado es divisible por K. De lo contrario , no es divisible por K.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check divisibility
bool checkIfDivisible(string str,
long long int num)
{
// Calculate the number of digits in num
long long int powerOf2 = log2(num);
// Check if the length of
// the string is less than
// the powerOf2 then
// return false
if (str.length() < powerOf2)
return false;
// Check if the powerOf2 is 0
// that means the given number
// is 1 and as every number
// is divisible by 1 so return true
if (powerOf2 == 0)
return true;
// Find the number which is
// formed by the last n digits
// of the string where n=powerOf2
long long int i, number = 0;
int len = str.length();
for (i = len - powerOf2; i < len; i++) {
number += (str[i] - '0')
* pow(10,
powerOf2 - 1);
powerOf2--;
}
// Check if the number formed is
// divisible by input num or not
if (number % num)
return false;
else
return true;
}
// Driver Code
int main()
{
// Given number
string str = "213467756564";
long long int num = 4;
// Function Call
if (checkIfDivisible(str, num))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to check divisibility
static boolean checkIfDivisible(String str,
long num)
{
// Calculate the number of digits in num
long powerOf2 = (int)(Math.log(num) /
Math.log(2));
// Check if the length of
// the string is less than
// the powerOf2 then
// return false
if (str.length() < powerOf2)
return false;
// Check if the powerOf2 is 0
// that means the given number
// is 1 and as every number
// is divisible by 1 so return true
if (powerOf2 == 0)
return true;
// Find the number which is
// formed by the last n digits
// of the string where n=powerOf2
long i, number = 0;
int len = str.length();
for(i = len - powerOf2; i < len; i++)
{
number += (str.charAt((int)i) - '0') *
Math.pow(10, powerOf2 - 1);
powerOf2--;
}
// Check if the number formed is
// divisible by input num or not
if (number % num != 0)
return false;
else
return true;
}
// Driver Code
public static void main(String[] args)
{
// Given number
String str = "213467756564";
long num = 4;
// Function call
if (checkIfDivisible(str, num))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program for the above approach
from math import log2
# Function to check divisibility
def checkIfDivisible(string, num):
# Calculate the number of digits in num
powerOf2 = int(log2(num));
# Check if the length of
# the string is less than
# the powerOf2 then
# return false
if (len(string) < powerOf2):
return False;
# Check if the powerOf2 is 0
# that means the given number
# is 1 and as every number
# is divisible by 1 so return true
if (powerOf2 == 0):
return True;
# Find the number which is
# formed by the last n digits
# of the string where n=powerOf2
number = 0;
length = len(string);
for i in range(length - powerOf2, length):
number += ((ord(string[i]) - ord('0')) *
(10 ** (powerOf2 - 1)));
powerOf2 -= 1;
# Check if the number formed is
# divisible by input num or not
if (number % num):
return False;
else :
return True;
# Driver Code
if __name__ == "__main__" :
# Given number
string = "213467756564";
num = 4;
# Function Call
if (checkIfDivisible(string, num)):
print("Yes");
else :
print("No");
# This code is contributed by AnkitRai01
C#
// C# program for the above approach
using System;
class GFG{
// Function to check divisibility
static bool checkIfDivisible(String str,
long num)
{
// Calculate the number of digits in num
long powerOf2 = (int)(Math.Log(num) /
Math.Log(2));
// Check if the length of
// the string is less than
// the powerOf2 then
// return false
if (str.Length < powerOf2)
return false;
// Check if the powerOf2 is 0
// that means the given number
// is 1 and as every number
// is divisible by 1 so return true
if (powerOf2 == 0)
return true;
// Find the number which is
// formed by the last n digits
// of the string where n=powerOf2
long i, number = 0;
int len = str.Length;
for(i = len - powerOf2; i < len; i++)
{
number += (long)((str[(int)i] - '0') *
Math.Pow(10, powerOf2 - 1));
powerOf2--;
}
// Check if the number formed is
// divisible by input num or not
if (number % num != 0)
return false;
else
return true;
}
// Driver Code
public static void Main(String[] args)
{
// Given number
String str = "213467756564";
long num = 4;
// Function call
if (checkIfDivisible(str, num))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript program for the above approach
// Function to check divisibility
function checkIfDivisible(str, num)
{
// Calculate the number of digits in num
let powerOf2 = (Math.log(num) /
Math.log(2));
// Check if the length of
// the string is less than
// the powerOf2 then
// return false
if (str.length < powerOf2)
return false;
// Check if the powerOf2 is 0
// that means the given number
// is 1 and as every number
// is divisible by 1 so return true
if (powerOf2 == 0)
return true;
// Find the number which is
// formed by the last n digits
// of the string where n=powerOf2
let i, number = 0;
let len = str.length;
for(i = len - powerOf2; i < len; i++)
{
number += (str[i] - '0') *
Math.pow(10, powerOf2 - 1);
powerOf2--;
}
// Check if the number formed is
// divisible by input num or not
if (number % num != 0)
return false;
else
return true;
}
// Driver Code
// Given number
let str = "213467756564";
let num = 4;
// Function call
if (checkIfDivisible(str, num))
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
Complejidad de tiempo: O (Len), donde Len es la longitud de la string.
Espacio Auxiliar: O(log 2 K)
Publicación traducida automáticamente
Artículo escrito por adeshsgaikwad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA