Last Updated: 7 Dec, 2020
Consecutive Numbers
Easy
Asked in companies
You are given a positive integer ‘N’. Find the smallest positive integer ‘K’ such that (‘K’ XOR ‘K-1’) equals ‘N’.
Here ‘XOR’ denotes the bitwise XOR operator denoted by ^.
If no such ‘K’ exists, return -1.
Input format :
The first line contains a single integer ‘T’ representing the number of test cases.Then test cases follows :
The first line of each test case contains an integer ‘N’.
Output Format :
For each test case, print the value of ‘K’ or -1 if no such ‘K’ exists.
Print the output of each test case in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 100
1 <= N <= 10^9
Time Limit : 1 sec
Approaches
Approach :
We will first assume that the value of K > N is valid.
So two cases arise here :
- All the bits left to N in K and (K-1) are the same.
In this case, we can always find some smaller positive integer as the leftmost bits are just added to small integers to make larger numbers. Since , if bits in both are same , their XOR will be 0.
E.g. Let K = 6 , then ( K - 1 ) = 5.
In binary representation, K = 110 and ( K - 1 ) = 101
Then K XOR ( K - 1 ) = 011, that is 3.
The same value can be received by taking K = 2, ( K - 1 ) = 1.
K XOR ( K - 1 ) = 011 , that is 3.
2. All the bits left to N in K and K-1 are not the same.
In this case, their XOR will be greater than K so it will never be equal to N.
Hence, we just need to check for K <= N if some valid integer is found such that K XOR ( K - 1 ) = N .
Algorithm :
- Run a for loop from ‘K’ =1 to ‘K’ = ‘N’.
- Inside this for loop :
- Check if current ‘K’ satisfies the equation K XOR ( K -1 ) = N.
- If Yes, we return this value of ‘K’.
- Otherwise, we keep incrementing the value of ‘K’.
- If we reach out of the for loop, no value of ‘K’ exists and we return -1.
Approach :
- Below are two cases when we do ( K ) XOR ( K - 1 ) for a number ‘K’ :
- Case 1 : ( K-1 ) is even.
Last bit of (K - 1) is 0 and the last bit of ‘K’ is 1. Rest of the bits are the same in both the numbers. So XOR would always be 1 if ( K-1 ) is even.
- Case 2 : ( K - 1 ) is odd
Last bit in ( K - 1 ) is 1. And in K, the last bit is 0.
But in this case there may be more bits which differ due to carry. The carry continues to propagate to the left till we find the first 0 bit. So (K) XOR ( K - 1) will be 2^i-1 where i is the position of the first 0 bit in ‘K’ from the left.
So, we can say that if N is of form 2^i-1 then we will have our answer as N/2+1.
- So, we just check if N is of the form 2^i - 1 :
- If Yes, we return ( N/2 + 1 ).
- Else, we return -1.
Algorithm :
- We check if N is of the form ( 2^x-1) :
- If ( N + 1 ) & N = 0, then N is of the form 2^x-1.
- We return answer as ( N / 2 + 1 )
- Else, we return -1.
- If ( N + 1 ) & N = 0, then N is of the form 2^x-1.