Check if Decimal representation of given Binary String is divisible by K or not
Given a binary string S, the task is to find that the decimal representation of the given binary string is divisible by integer K or not.
Examples:
Input: S = 1010, k = 5
Output: Yes
Explanation: Decimal representation of 1010 (=10) is divisible by 5Input: S = 1010, k = 6
Output: No
Approach: Since the modulo operator is distributive over addition, the given binary string can be checked bit by bit to see whether the decimal % k is equal to zero or not. Follow the steps below for the approach:
- Initialize an array poweroftwo[], of size of binary string, to store the powers of two.
- Iterate till size and for each i store 2i % K in poweroftwo[].
- Initialize variables, say rem = 0, to store the current remaining number till i.
- Iterate till size and for each i and if S[size – i -1] is 1 then update rem equals rem + poweroftwo[i].
- Finally, return Yes if rem equals zero else return No.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to check the binary number is // divisible by K string divisibleByk(string s, int n, int k) { // Array poweroftwo will store pow(2, i)%k int poweroftwo[n]; // Initializing the first element in Array poweroftwo[0] = 1 % k; for ( int i = 1; i < n; i++) { // Storing every pow(2, i)%k value in // the array poweroftwo[i] = (poweroftwo[i - 1] * (2 % k)) % k; } // To store the remaining int rem = 0; // Iterating till N for ( int i = 0; i < n; i++) { // If current bit is 1 if (s[n - i - 1] == '1' ) { // Updating rem rem += (poweroftwo[i]); rem %= k; } } // If completely divisible if (rem == 0) { return "Yes" ; } // If not Completely divisible else return "No" ; } // Driver Code int main() { // Given Input string s = "1010001" ; int k = 9; // length of string s int n = s.length(); // Function Call cout << divisibleByk(s, n, k); return 0; } |
Java
// Java program for above approach class GFG { // Function to check the binary number is // divisible by K public static String divisibleByk(String s, int n, int k) { // Array poweroftwo will store pow(2, i)%k int [] poweroftwo = new int [n]; // Initializing the first element in Array poweroftwo[ 0 ] = 1 % k; for ( int i = 1 ; i < n; i++) { // Storing every pow(2, i)%k value in // the array poweroftwo[i] = (poweroftwo[i - 1 ] * ( 2 % k)) % k; } // To store the remaining int rem = 0 ; // Iterating till N for ( int i = 0 ; i < n; i++) { // If current bit is 1 if (s.charAt(n - i - 1 ) == '1' ) { // Updating rem rem += (poweroftwo[i]); rem %= k; } } // If completely divisible if (rem == 0 ) { return "Yes" ; } // If not Completely divisible else return "No" ; } // Driver Code public static void main(String args[]) { // Given Input String s = "1010001" ; int k = 9 ; // length of string s int n = s.length(); // Function Call System.out.println(divisibleByk(s, n, k)); } } // This code is contributed by _saurabh_jaiswal, |
Python3
# python 3 program for above approach # Function to check the binary number is # divisible by K def divisibleByk(s, n, k): # Array poweroftwo will store pow(2, i)%k poweroftwo = [ 0 for i in range (n)] # Initializing the first element in Array poweroftwo[ 0 ] = 1 % k for i in range ( 1 ,n, 1 ): # Storing every pow(2, i)%k value in # the array poweroftwo[i] = (poweroftwo[i - 1 ] * ( 2 % k)) % k # To store the remaining rem = 0 # Iterating till N for i in range (n): # If current bit is 1 if (s[n - i - 1 ] = = '1' ): # Updating rem rem + = (poweroftwo[i]) rem % = k # If completely divisible if (rem = = 0 ): return "Yes" # If not Completely divisible else : return "No" # Driver Code if __name__ = = '__main__' : # Given Input s = "1010001" k = 9 # length of string s n = len (s) # Function Call print (divisibleByk(s, n, k)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for above approach using System; class GFG { // Function to check the binary number is // divisible by K public static String divisibleByk(String s, int n, int k) { // Array poweroftwo will store pow(2, i)%k int [] poweroftwo = new int [n]; // Initializing the first element in Array poweroftwo[0] = 1 % k; for ( int i = 1; i < n; i++) { // Storing every pow(2, i)%k value in // the array poweroftwo[i] = (poweroftwo[i - 1] * (2 % k)) % k; } // To store the remaining int rem = 0; // Iterating till N for ( int i = 0; i < n; i++) { // If current bit is 1 if (s[n - i - 1] == '1' ) { // Updating rem rem += (poweroftwo[i]); rem %= k; } } // If completely divisible if (rem == 0) { return "Yes" ; } // If not Completely divisible else return "No" ; } // Driver Code public static void Main(String []args) { // Given Input String s = "1010001" ; int k = 9; // length of string s int n = s.Length; // Function Call Console.Write(divisibleByk(s, n, k)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // Javascript program for above approach // Function to check the binary number is // divisible by K function divisibleByk(s, n, k) { // Array poweroftwo will store pow(2, i)%k let poweroftwo = new Array(n); // Initializing the first element in Array poweroftwo[0] = 1 % k; for (let i = 1; i < n; i++) { // Storing every pow(2, i)%k value in // the array poweroftwo[i] = (poweroftwo[i - 1] * (2 % k)) % k; } // To store the remaining let rem = 0; // Iterating till N for (let i = 0; i < n; i++) { // If current bit is 1 if (s[n - i - 1] == '1' ) { // Updating rem rem += (poweroftwo[i]); rem %= k; } } // If completely divisible if (rem == 0) { return "Yes" ; } // If not Completely divisible else return "No" ; } // Driver Code // Given Input let s = "1010001" ; let k = 9; // length of string s let n = s.length; // Function Call document.write(divisibleByk(s, n, k)); // This code is contributed by gfgking. </script> |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us