Consecutive Numbers

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
QualcommAmazon

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
1
2
Sample Output 1:
1
-1
Explanation For Sample Input 1 :
For the first test case, we have, ‘N’ = 1.
First we try ‘K’ = 1.
‘K’ XOR ‘K-1’ = ‘1’ XOR ‘0’ = 1.
Hence, the smallest positive integer is 1. 

For the second test case, we have, ‘N’ = 2.
First we try ‘K’ = 1.
‘K’ XOR ‘K-1’ = 1^0 = 1.
Next we try ‘K’ = 2.
‘K’ XOR ‘K-1’ = 2^1 = 3.
Similarly, trying for all possible values , we see that no such number exists.
Sample Input 2 :
2
3
7
Sample Output 2 :
2
4
Hint

Do we need to check values for ‘K’ > ’N’ ?

Approaches (2)
Brute Force

Approach : 
 

We will first assume that the value of K > N is valid.
 

So two cases arise here : 

 

  1. 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.
Time Complexity

O( N ), where ‘N’ is the given input.
 

Since we run a for loop from K=1 to K = N , the overall time complexity will be O(N)

Space Complexity

O(1)
 

Constant extra space is required.

Code Solution
(100% EXP penalty)
Consecutive Numbers
Full screen
Console