Find the lone set bit

INPUT : N = 4 OUTPUT : 3 In the above example, N = 4, whose Binary representation is “0100”. It is clearly visible that the binary number contains a single set bit, at a position 3 from the LSB end. Hence the output is 3 INPUT : N = 8 OUTPUT: 4 In the above example, N = 8, whose Binary representation is “1000”. It is clearly visible that the binary number contains a single set bit, at a position 4 from the LSB end. Hence the output is 4 INPUT : N = 9 OUTPUT : -1 In the above example, N = 9, whose Binary representation is “1001”. Now, the binary number contains 2 set bits, at a position 4 and 1 from LSB end. Hence the output is -1. INPUT : N = 0 OUTPUT : -1 In the above example, N = 0, whose Binary representation is “0000”. Now, the binary number contains no set bits at all. Hence the output will be -1.

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows. The first and the only line of each test case contains a single integer ‘N’.

In the first test case, N = 2, whose Binary equivalent is “10”. The set bit is at position 2 from the LSB end. Hence the output is 2 In the second test case, N = 8, whose Binary equivalent is “1000”. The set bit is at position 4 from the LSB end. Hence the output is 4 In the third test case, K = 11, whose Binary equivalent is “1011”. The count of the total number of set bits is 3 which is not equal to 1. Hence the output is -1 In the fourth test case, K = 0, whose Binary equivalent is “0000”, which contains no set bits at all. Hence the output is -1.

Approach 1

If we observe a little, we can clearly see that only those integers, which can be represented as a power of 2 have a single set bit in their binary equivalent, and rest either have 0 or more than 1 set bits. Now, we only have to work on the integers which are a power of 2. We will start from the LSB end or the rightmost bit, and check every bit one by one.

We are given a function findSetBit(), which takes a single integer ‘N’ which is our input integer as the parameter, and returns a single integer.
To check if the input integer ‘N’ is a power of 2 or not, we create another function isPower2(), which takes a single integer as the parameter and returns either true or false. This function is based on the logic that an integer ‘N’ will be a power of 2 if the bitwise AND of N and N - 1 will be zero.
We call the function isPower2() on our input integer ‘N’, to check whether it can be represented as a power of 2. If it is not a power of 2, we return -1.
If ‘N’ is a power of 2, we proceed by declaring two variables, ‘J’ as our loop variable and ‘P’ which will store the position of the set bit. Initialize both of them as 1.
In the loop, we perform bitwise AND operation of integer ‘J’ and ‘N’. If the operation returns TRUE, it means that the current bit ‘P’ is a set bit, hence we break the loop and return ‘P’.
If the operation returns FALSE, we set the next bit in ‘J’ by doing a left shift on ‘J’ by 1. Along with that, we increment ‘P’ by 1 to move to the next position from LSB. The loop keeps on repeating the procedure until it encounters a set bit and returns ‘P’ as the answer.

Time Complexity

O(log(N)), where N is the input integer.

In the worst case, the loop will run until J = N doing a left shift operation at each step. So a total of log(N) steps will take place. The function isPower2() also runs in log(N) time. Hence the overall time complexity is O(log(N)).

Space Complexity

O(1)

As we are not using any extra space so we have a constant space complexity.

Problem statement

Sample Input 1:

Sample Output 1:

Explanation For Sample Input 1:

Sample Input 2:

Sample Output 2: