Bitwise Operators: Given a binary string, check the divisibility of the string by 2^k

Problem Statement:

You are given an binary string, you need to check if the binary string is evenly divisible bt 2^k or not

Example:

Input: 11000 K = 2

Output: yes

11000 in decimal is 24

and 24 is evenly divisible by 2^2 i.e 4

Solution 1: Naive Approach

Convert the binary string into decimal by iterating over each digit from left to right

Calculate the value of 2^k using bitwise left shift operation

Then do the modulus operation and check if its 0, then return true else false.

Time Complexity: O(n)
Space Complexity: O(1)

Solution 2: Efficient Approach

Check the last k bits of the string.

if all the last k bits are 0, then the binary number is divisible by 2^k else its not divisible.

Time Complexity: O(1k)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

bool solution_1(char str[], int k)
{
    int in_decimal = 0;
    int base = 1;
    int n = strlen(str);
    
    for (int i = n - 1; i >= 0; i--) 
    {
        if (str[i] == '1') {
            in_decimal += base;
        }
        base *= 2;
    }
 
    return (in_decimal % (1 << k)) == 0;
}

bool solution_2(char str[], int k)
{
    int n = strlen(str);
    int count = 0;
     
    for (int i = 0; i < k; i++) 
    { 
        if (str[n - i - 1] == '0')
        {        
            count++;
        }
    }

    return (count == k);
}
int main()
{

    char str1[] = "10101100";
    int k = 2;
    if (solution_1(str1, k))
        cout << "Yes" << endl;
    else
        cout << "No";
    
    cout << "\n";
             
    if (solution_2(str1, k))
        cout << "Yes" << endl;
    else
        cout << "No";
    return 0;
}

Output

Yes

Yes