Check whether K-th bit is set or not

Easy

0/40

Contributed by

80 upvotes

Problem statement

Given a number ‘N’ and a number ‘K’. Return true if ‘K’th bit of number is set, else return false.

Example:

Input: ‘N’ = 5, ‘K’ = 1

Output: YES

5 in binary can be written as 101 and as we can see a first bit from the right of 5 is set so the answer is 'YES'.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains two integers ‘N’ and ‘K’ respectively.

Output format :

The only line contains 'YES', if the 'K-th' bit is set, else 'NO'.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Sample Input 1 :

3 2

Sample Output 1 :

YES

Explanation Of Sample Input 1 :

3 in binary can be represented as 11 and 2 bit from right is set there, So answer is 'YES'.

Sample Input 2 :

128 7

Sample Output 2 :

NO

Constraints :

1 <= N <= 10^9
1 <= K <= 20

Time Limit: 1 sec

Hint 1

Hint 2

Left Shift.

Approaches (2)

Approach 1

Approach 2

Left Shift

Bitwise and of two bits is true if both bits are high. Left shift operation shifts the bit left by a given number so left shift by K is like 2^K so what we can do is we can shift 1 to the left by k-1 which makes it 2^(K-1) and we do the bitwise and of this with number ‘N’ which result in 2^(K-1) if kth bit is set else it becomes 0. We are reducing K to K-1 because bits start from 0.

The steps are as follows:-

Bitwise and of 2 bits is true if both bits are true else it is false.
So we can check the bitwise and of n and 2^(K-1).
Return True if the bitwise and is equal to 2^(K-1) then return True else return False.

Time Complexity

O(1).

Since all these operations are constant-time, the overall time complexity of the function remains O(1).

Hence time complexity will be O( 1 ).

Space Complexity

O( 1 )

As we are using no extra space.Hence space complexity is O( 1 ).

(100% EXP penalty)

Check whether K-th bit is set or not

Console