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:

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

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.

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

Complexity

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. 数组异或操作

Previous1482. Minimum Number of Days to Make m BouquetsNext1539. Kth Missing Positive Number

Last updated

Was this helpful?