Time Complexity: O(logN), we convert the given number into its binary representation.
Space Complexity: O(logN), additonal space is used to store the binary representation.

Optimal Approach

Algorithm

In a number’s binary representation, each bit corresponds to a power of 2. To check if the ith bit is set, instead of converting the number to binary and manually checking, we can use bitwise operators. By left-shifting 1 by i positions, we create a mask that has only the ith bit set. Performing a bitwise AND between the number and this mask will isolate the ith bit. If the result is non-zero, the ith bit was set, otherwise it was not. This avoids extra space and makes the check more efficient.

Take the number and bit index as input.

Code

12