Given an integer n and an integer start .
Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length .
Return the bitwise XOR of all elements of nums .
How to do this in O(1)
Some kind of pattern appears after first four terms(a1,a2,a3,a4),
(ai=xor of all elements from 1 to i)(1 based indexing)
a5=a1+8
a6=a2
a7=a3+8
a8=a4
…
or
a(i)=a(i-4)+8 if(i%4==1)
a(i)=a(i-4) if(i%4==2)
a(i)=a(i-4)+8 if(i%4==3)
a(i)=a(i-4) if(i%4==0)
and so on.
So you can calculate first four terms and use this pattern to calculate required.
I am not sure about the proof if anyone can prove it, it would be more intuitive.
Edit: I think this is wrong.Sorry for trouble.I don’t see any O(1) solution so easily.
1 Like
Let’s try to solve a simple Problem:
What is the bitwise xor of even numbers in range [0, n], assuming n is even. If n is odd, just subtract 1. We will solve this problem in O(log(n)).
Let’s look at the i^{th} bit from right(LSB side) and see how many numbers have this bit set. Try to prove 1. and 2. and solve from 3.
1. i^{th} bit flips after every 2^i numbers. That is suppose i^{th} bit was set in some number x, then this bit is not set in x+2^i and vice-versa.
2. From 1 we see that in the first 2^{i+1} numbers(count starts from 0), i^{th} bit was set in 2^i numbers, therefore total number of even numbers which have i^{th} bit set is 2^{i-1}. Special Case : i = 0, where total even numbers would be 0.
3. From 2 we see that i^{th} bit is set in even numbers(except i = 1 case), therefore we need to search in between \lfloor\frac{n}{2^{i+1}}\rfloor * 2^{i+1} and n, since all other vanishes. For this you need to check the difference between n and \lfloor\frac{n}{2^{i+1}}\rfloor * 2^{i+1}. If this difference is less than 2^i continue to next bit else find even numbers in range \lfloor\frac{n}{2^{i+1}}\rfloor * 2^{i+1} + 2^i to n since these numbers have i^{th} bit set. If these numbers are found to be odd, then you add 2^i to the answer.
To solve the original problem, you can use solve(start+2*(n-1)) \oplus solve(start-1), where solve(n) solves for range [0, n], if start is even and if start is odd you can come up with a similar maths.
If anything is unclear, do tell me. Btw, why do you require O(1) solution?
2 Likes
Can plz prove 1?
This question was from a contest in leetcode, the follow up was O(1)…
Suppose that i^{th} bit was set in x, then x = y + 2^i, where i^{th} bit is not set in y, therefore x + 2^i = y + 2^{i+1} which means bit greater than i can only change and i^{th} bit vanishes. Start from smallest value, x = 0, it does not have the bit set, therefore next number in which i^{th} bit is set is 2^i. The next number in which this bit is not set is 2^i + 2^i = 2^{i+1}. Hoping this helped.
1 Like
Actually when I solve problems of XOR, AND, OR, I try to work with bits. O(1) solution would be like finding the pattern(which I don’t like). No one sets a hard TL for which O(1) works but O(log(n)) gives TLE.
1 Like
Link to question?
tnx, but i still don’t get some of it…
1. Therefore x + 2^i = y + 2^{i+1} which means bit greater than i can only change
2. Start from smallest value, x = 0.... So here when X=0, the equal is something like
2^i = y + 2^{i+1} how are you concluding that the next number in which " "" " is 2^i....