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)

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