I saw some solutions where programmers were checking if input was a power of 2, then there were printing n/2 as there answer and -1 otherwise except in the case of n=1.
Why it is so? Is this a property of XOR ?
Can anybody provide a little insight on this or a reference to the reason we solved this way.
Some Observations:
0.Obviously one of M and M+1 is odd, therefore one has 0 as LSB and other has 1 as LSB
1.Even numbers can’t be obtained by consecutive Xoring because even numbers have zero as LSB , which can’t be obtained with respect to property 0.
2.Next with some trial and experimentation
1^2 = 3
2^3 = 1
3^4 = 7
4^5 = 1
5^6 = 3
6^7 = 1
7^8 = 15
…
Numbers which can be obtained by consecutive xoring are 1,3,7,15,… i.e in binary 1,11,111,1111,…
Hence all other numbers should be answered -1
Since all bits are 1,the operands must have all bits different at each position
Numbers which are consecutive and have all bits different are (0,1),(1,2),(3,4),(7,8),… yielding 1,3,7,15,…
therefore the answer is directly n>>1 with ‘1’ being exception and is to answered ‘2’ from above trial answers
yeah, ((M) XOR (M+1) is always of the form (2^k - 1) hence the number should be always of the form 2^k-1 otherwise we have to print -1 and to check if number is of form 2^k-1 we can AND number ie. 2^k-1 with number+1 ie. 2^k and if result is ‘0’ than it is of form 2^k-1 otherwise not because 2^k-1 = {01111…} and 2^k will be = {10000…} and hence AND will give ‘0’.
//simple and short code …is not it???
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
long long int n;
while(t--){
cin>>n;
cout<<(( (n&(n+1))!= 0) ? -1 :( (n!=1) ? n>>1: 2))<<endl;
}
return 0;
}
HAPPY CODING
hi…
you can make try any two number M ^ (M+1) always you get number in form of 2^k-1 as @chiragjn and @glow for testing this you can just run a loop to checking this.
hope you got it…
I think the others have answered it well. I’m just adding a point that during the contest, I checked the XOR of consecutive numbers upto 16 (like @chiragjn has showed).
And i was rational about whether the hypothesis that *Only number of the form 2^i-1 could be formed by XOR of consecutive two natural numbers. (i being a natural no.) * was true or not. So I checked using the a brute force till 2^10=1024.
Detailed analysis:
Given N, find smallest value of X such that X^(X+1)=N (where ^ is XOR and X>0).
If X is even, therefore X+1 is odd.
In this case the X^(X+1) = 1. It is because only the LSB is changed in the binary representation.
X is odd, X+1 is even. We can see that that X^(X+1) is the same value as the number of contiguous 1’s in the binary representation of X.
This means that N must be of form 111…111 otherwise its not possible.
In this case, we do a right shift ans=(N>>1);
4. The tricky case is of 1. We know that 0^1 = 1. So according to the above logic, X=0 but
as X>0 constraint is not satisfied. We check for other ans. As 2^3 = 1, thus for case N=1, ans=2.
5. Now we can check whether a no. N is of the form of 2^i-1 by various methods like: Binary representation contains all 1, or a better one: The truth value of (N & (N+1)) equals 0.
Here: ACed solution Do have a look at the answer.
can anyone tell me why it is giving wrong answer?
import math t = int(raw_input()) while(t): n = int(raw_input()) n += 1 if(n==2): print 2 elif(math.ceil(math.log(n,2))== math.log(n,2)): print int(math.pow(2,int(math.ceil(math.log(n,2)))-1)-1) else: print -1 t-=1
Hey, it’s not just simple coincidence that M^(M+1) becomes of the form 2^k-1.
Let me explain in the best way I can. I’ll do that in two parts.
Part 1:
Observe:
11 or 111 or 11111 what’s special about them…
If you convert them into decimal, they will become(I’m writing for 11111)
2^4+2^3+2^2+2^1+2^0, which will evaluate to
2^0(2^5-1)/(2-1)…(as per the Geometric Progression formula).(a(r^n-1)/(r-1)).
And this happens only when there are continuous 1’s.(this should be clear by now)
Part 2:
Okay now the second part:
What does M^(M+1): this would be much more clear if you know binary addition.
Let M be 1110000111
So to know how M+1 looks like lets add “1” to “1110000111”
1110000111
0000000001
1110001000
So you see the last continuous 1’s(until there is one zero 1110000"111" ) have been flipped into 0’s
and this happens only till the first zero (in our case it is the fourth digit from right) and this zero itself
is flipped into a 1.
Now if you notice that since things get flipped, and if we XOR them they simply get added…
HOPE you understood, if you still find anything confusing, ask here itself…
HAPPY CODING
wow …