Find the lone set bit
You are given a single non-negative integer ‘N’ who’s binary representation consists of a single ‘1’ digit and the rest of the digits are ‘0’s. Your task is to find the position of the only ‘1’ digit. In other words, your task is to find the position of the only set bit in the binary representation of the input integer ‘N’.

The position of the set bit must be counted from the LSB (Least Significant Bit) end of the Binary number. If the count of set bits in the Binary number is not equal to 1, then your function should return ‘-1’ as output.

Example:-

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.

Input Format

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’.

Output Format:

For every test case, print a single integer, which is the position of the lone set bit in the binary representation of the input integer ‘N’.

Note:

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Find the lone set bit

You are given a single non-negative integer ‘N’ who’s binary representation consists of a single ‘1’ digit and the rest of the digits are ‘0’s. Your task is to find the position of the only ‘1’ digit. In other words, your task is to find the position of the only set bit in the binary representation of the input integer ‘N’.

The position of the set bit must be counted from the LSB (Least Significant Bit) end of the Binary number. If the count of set bits in the Binary number is not equal to 1, then your function should return ‘-1’ as output.

Example:-

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.

Input Format

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’.

Output Format:

For every test case, print a single integer, which is the position of the lone set bit in the binary representation of the input integer ‘N’.

Note:

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100    
0 <= N <= 10^5

Time limit: 1 second

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(logn)Explanation:

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)).

Accepted Answer

Approach 2

We know that the only set bit will always be the leftmost bit or the MSB (Most Significant Bit). So in this approach, we will perform the right shift operation on the only set bit of ‘N’ by 1, until it becomes ‘0’ also keeping the count of each shift. The final value of the count will be the position of the set bit.

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 it is a power of 2, we proceed by declaring a variable “COUNTER” and initializing it with 0.
In the loop, right shift N by 1, and simultaneously increment the “COUNTER”, until N becomes 0.
After the loop breaks, return “COUNTER” which contains our final answer.

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(logn)Explanation:

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

At each step of your function, our number is getting divided by 2 due to the right shift operation. Hence the while loop will run a total log(N) times.The function isPower2() also runs in log(N) time. So the overall time complexity is O(log(N)).

Accepted Answer

Approach 3

If the integer is the power of 2, then finding the Log of the base 2, of the input integer N, and incrementing it by 1 will give the position of its set bit. If the integer is a power of two, then its log to the base 2 will give the count of 0s in its binary representation. Hence incrementing it by 1 will be the position of the set bit.

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.
To find the log to the base 2 of N, we create another function log2N() which takes an integer as the only parameter and returns another integer. This function will recursively compute the log to the base 2 and return it.
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 it is a power of 2, we proceed by calling our function log2N() and return it by incrementing by 1. It is our final answer.

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(logn)Explanation:

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

Both our functions isPower2() and log2N() run in log(N) time. Hence our overall time complexity is O(log(N)).

The position of the set bit must be counted from the LSB (Least Significant Bit) end of the Binary number. If the count of set bits in the Binary number is not equal to 1, then your function should return ‘-1’ as output.

Example:-

Input Format

Output Format:

Note:

Constraints:

Top BugsMirror Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern