Given a large number in the form of a string str and a number K, the task is to check if the number formed by string str is divisible by the K or not, where K is a power of 2.
Examples:
Input: str = “5426987513245621541524288”, num = 64
Output: Yes
Explanation:
Since log2(64) = 6, so the number formed by the last 6 digits from the string str is divisible by 64 .
Input: str = “21346775656413259795656497974113461254”, num = 4
Output: No
Explanation:
Since log2(4)=2, the number formed by the last 2 digits from the string str is not divisible by 4.
Approach:
Since K is a perfect power of 2. Let K can be represented as 2X. Then according to the divisibility rule of perfect power of 2, if the last X digit of the given number is divisible by K then the given number is divisible by K. Otherwise it is not divisible by K.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h> using namespace std;// Function to check divisibilitybool 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 Codeint 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 approachclass GFG{ // Function to check divisibilitystatic 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 Codepublic 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 approachusing System;class GFG{ // Function to check divisibilitystatic 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 Codepublic 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 divisibilityfunction 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> |
Output:
Yes
Time Complexity: O(Len), where Len is the length of the string.
Auxiliary Space: O(log2K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
