1486. XOR Operation in an Array

LeetCode 1486. XOR Operation in an Array

Description

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.

Example 1:

Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8.
Where "^" corresponds to bitwise XOR operator.

Example 2:

Input: n = 4, start = 3
Output: 8
Explanation: Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8.

Example 3:

Input: n = 1, start = 7
Output: 7

Example 4:

Input: n = 10, start = 5
Output: 2

Constraints:

• 1 <= n <= 1000

• 0 <= start <= 1000

• n == nums.length

Tags

Array, Bit Manipulation

Solution

We can reduce the time complexity through mathematical operations.

Before we do that, let's review some characters of XOR:

1. $x⊕x=0$ ;

2. $x⊕y=y⊕x$;

3. $(x⊕y)⊕z=x⊕(y⊕z)$ ;

4. $x⊕y⊕y=x$ ;

5. $∀i∈Z， 4i \oplus (4i+1) \oplus (4i+2) \oplus (4i+3) = 0$;

6. $N \oplus (N+1) \oplus ... \oplus M = [1 \oplus 2 \oplus ... \oplus (N+1)] \oplus [1 \oplus ... \oplus M-1 \oplus M]$ .

To make use of the 5th property of XOR, we mutate the required function to:

$start⊕(start+2i)⊕(start+4i)⊕⋯⊕(start+2(n−1)) \Leftrightarrow (s⊕(s+1)⊕(s+2)⊕⋯⊕(s+n−1))×2+e, s=⌊ start/2 ⌋, e = n\&start\&1$

In this formula, e is the lowest bit and it is equal to 1 if and only if n and start are both odd numbers.

To obtain $temp = (s⊕(s+1)⊕(s+2)⊕⋯⊕(s+n−1))$ , based on the property 6, we only need to compute $[1 \oplus 2 \oplus ... \oplus (s-1)] \oplus [1 \oplus ... \oplus (s-n+1)]$ . Note that the pattern of XOR of the first n numbers is n, 1, n+1, 0.

Finally, we return the recovered result temp * 2 + e.

Complexity

• Time complexity: $O(1)$

• Space complexity: $O(1)$

Code

func xorOperation(n int, start int) int {
	// the lowest bit is 1 if and only if n and start are both odd numbers
	lowestBit := n & start & 1

	// start ^ (start+2) ^ (start+4) ^ ... ^(start + 2*(n-1))
	// let s = start / 2
	// <=> (s ^ (s+1) ^ (s+2) ^ ... ^ (s+n-1)) * 2 + lowestBit
	s := start >> 1

	// ^(N ... M) = ^(1 ... N-1) ^ ^(1 ... M)
	temp := computeXOR(s-1) ^ computeXOR(s+n-1)
	return temp<<1 | lowestBit
}

func computeXOR(x int) int {
	// The pattern of XOR of the first n numbers
	//      n   binary ^(0...N)   return
	//      1    0001    0001        1
	//      2    0010    0011       n+1
	//      3    0011    0000        0
	//      4    0100    0100        n
	//      5    0101    0001        1
	//      6    0110    0111       n+1
	//      ……   ……      ……
	switch x % 4 {
	case 0:
		return x
	case 1:
		return 1
	case 2:
		return x + 1
	default: // 3
		return 0
	}
}

Reference

1. 小明做数学

2. 数组异或操作