XOR Operation in an Array

Difficulty: Easy | Acceptance: 87.60% | Paid: No Topics: Math, Bit Manipulation

You are given an integer n and an integer start.

Define an array nums where nums[i] = start + 2 * i (0-indexed) and 0 <= i < n.

Return the bitwise XOR of all elements of nums.

• Examples
• Constraints
• Approach 1: Simulation
• Approach 2: Mathematical Optimization

Examples

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.

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

Constraints

- 1 <= n <= 1000
- 0 <= start <= 1000
- n == nums.length

Approach 1: Simulation

Intuition The most straightforward approach is to simulate the process described in the problem. We iterate through the range [0, n-1], calculate the value for each index using the formula start + 2 * i, and accumulate the result using the bitwise XOR operation.

Steps

• Initialize a variable ans to 0.
• Loop from i = 0 to n - 1.
• In each iteration, update ans by performing XOR with start + 2 * i.
• Return ans after the loop finishes.

class Solution:
    def xorOperation(self, n: int, start: int) -> int:
        ans = 0
        for i in range(n):
            ans ^= start + 2 * i
        return ans

Complexity

• Time: O(n) - We iterate through the loop n times.
• Space: O(1) - We only use a single variable to store the result.
• Notes: This approach is simple and efficient enough given the constraints (n <= 1000).

Approach 2: Mathematical Optimization

Intuition We can solve this problem in O(1) time using mathematical properties of XOR. The sequence start, start + 2, ..., start + 2*(n-1) is an arithmetic progression. We can separate the problem based on whether start is even or odd. If start is even, all numbers are even, and the result is simply 2 * XOR(start/2, start/2 + n - 1). If start is odd, all numbers are odd, and the result is (2 * XOR(start//2, start//2 + n - 1)) | (n % 2). The XOR of a range [0, k] follows a pattern based on k % 4.

Steps

• Define a helper function computeXOR(k) that returns XOR of all numbers from 0 to k.
  • If k % 4 == 0, return k.
  • If k % 4 == 1, return 1.
  • If k % 4 == 2, return k + 1.
  • If k % 4 == 3, return 0.
• Calculate s = start // 2 and e = s + n - 1.
• Calculate total_xor = computeXOR(e) ^ computeXOR(s - 1).
• If start is even, return total_xor * 2.
• If start is odd, return total_xor * 2 ^ (n % 2).

class Solution:
    def xorOperation(self, n: int, start: int) -> int:
        def computeXOR(n):
            if n % 4 == 0: return n
            if n % 4 == 1: return 1
            if n % 4 == 2: return n + 1
            return 0

        s = start // 2
        e = s + n - 1
        total_xor = computeXOR(e) ^ computeXOR(s - 1)

        if start % 2 == 0:
            return total_xor * 2
        else:
            return total_xor * 2 ^ (n % 2)

Complexity

• Time: O(1) - We perform a constant number of arithmetic operations.
• Space: O(1) - We use a constant amount of extra space.
• Notes: This approach is optimal for very large values of n, though the problem constraints are small enough that the simulation approach is also acceptable.