# XOR Operation in an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/xor-operation-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/xor-operation-in-an-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## Problem
You are 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.

**Constraints:**

* `1 <= n <= 1000`
* `0 <= start <= 1000`
* `n == nums.length`

# Approaches
## Simple Iteration
This approach directly simulates the process described in the problem. We generate each number in the sequence and accumulate the XOR sum in a loop.
**Time:** O(n) - The algorithm involves a single loop that runs `n` times. All operations inside the loop are constant time. · **Space:** O(1) - We only use a few variables to store the result and loop counter, regardless of the input size `n`. We do not explicitly construct the array.
**Pros:** Very simple to understand and implement.; Directly translates the problem description into code.; Sufficiently fast for the given constraints (n <= 1000).
**Cons:** Not the most optimal solution in terms of time complexity.; Would be too slow if `n` were much larger.
### Explanation
We initialize a variable, say `result`, to 0. Then, we iterate from `i = 0` to `n-1`. In each step of the loop, we calculate the current element of the array `nums` using the formula `num = start + 2 * i`. We then update our `result` by performing a bitwise XOR operation with the current number: `result = result ^ num`. After the loop completes, `result` will hold the bitwise XOR of all elements, which we then return. This method avoids explicitly creating and storing the `nums` array, thus saving space.

```java
class Solution {
    public int xorOperation(int n, int start) {
        int xorResult = 0;
        for (int i = 0; i < n; i++) {
            int currentNum = start + 2 * i;
            xorResult ^= currentNum;
        }
        return xorResult;
    }
}
```
### Algorithm
- Initialize a variable `xorResult` to 0.
- Loop for `i` from 0 to `n-1`:
    - Calculate the current number `currentNum = start + 2 * i`.
    - Update the result: `xorResult = xorResult ^ currentNum`.
- After the loop, return `xorResult`.

## Constant Time Mathematical Approach
A more advanced approach involves mathematical and bitwise manipulation to compute the result in constant time, O(1). This method avoids iteration by analyzing the properties of the XOR operation on an arithmetic progression.
**Time:** O(1) - The solution involves a fixed number of arithmetic and bitwise operations, regardless of the value of `n`. · **Space:** O(1) - Only a few variables are used for calculations.
**Pros:** Extremely efficient, providing a constant time solution.; Demonstrates a deep understanding of bitwise operations and mathematical patterns.
**Cons:** The logic is significantly more complex to derive and understand.; Might be considered overkill given the small constraints of the problem.
### Explanation
The core idea is to decompose the problem by looking at the bits. Each number in the sequence is `start + 2*i`.
Let's analyze the structure of these numbers. Let `s = start >> 1` and `e = start & 1`. Then `start = 2*s + e`. The `i`-th term is `2*s + e + 2*i = 2*(s+i) + e`.

The final XOR sum can be broken down into two parts:
1.  **The Least Significant Bit (LSB):** The LSB of each term `2*(s+i) + e` is simply `e`. We are XORing `e` with itself `n` times. The result is `e` if `n` is odd, and `0` if `n` is even. This can be calculated as `(n & 1) & e`, or `(n & 1) & (start & 1)`.

2.  **The Higher Bits:** The higher bits of the XOR sum come from the `2*(s+i)` parts. The XOR sum of these is `(2*s) ^ (2*(s+1)) ^ ... ^ (2*(s+n-1))`. Using the property `(a << 1) ^ (b << 1) = (a ^ b) << 1`, this simplifies to `(s ^ (s+1) ^ ... ^ (s+n-1)) << 1`.

The sum `s ^ (s+1) ^ ... ^ (s+n-1)` is an XOR sum of a contiguous range of integers. This can be computed efficiently using a helper function, `prefixXor(x)`, which calculates `0 ^ 1 ^ ... ^ x`. The XOR sum of a range `[a, b]` is `prefixXor(b) ^ prefixXor(a-1)`. The `prefixXor(x)` function itself can be implemented in O(1) time based on the value of `x % 4`.

By combining the results from the LSB and the higher bits, we can find the final answer in constant time.

```java
class Solution {
    // Helper function to compute 0^1^...^x in O(1)
    private int prefixXor(int x) {
        if (x < 0) {
            return 0;
        }
        switch (x % 4) {
            case 0: return x;
            case 1: return 1;
            case 2: return x + 1;
            case 3: return 0;
        }
        return 0; // Should not be reached
    }

    public int xorOperation(int n, int start) {
        int s = start >> 1;
        int e = start & 1;

        // XOR sum of s, s+1, ..., s+n-1
        int rangeXor = prefixXor(s - 1) ^ prefixXor(s + n - 1);
        
        // Higher bits part
        int higherBits = rangeXor << 1;
        
        // LSB part
        int lsb = (n & 1) & e;
        
        return higherBits | lsb;
    }
}
```
### Algorithm
- Define a helper function `prefixXor(x)` that computes `0 ^ 1 ^ ... ^ x` in O(1).
- Calculate `s = start >> 1`.
- Calculate the XOR sum of the range `[s, s + n - 1]` as `rangeXor = prefixXor(s - 1) ^ prefixXor(s + n - 1)`.
- The contribution from the higher bits is `higherBits = rangeXor << 1`.
- The contribution from the least significant bit is `lsb = (n & 1) & (start & 1)`.
- The final result is `higherBits | lsb`.

# Solutions
### Java

```java
class Solution {
public
  int xorOperation(int n, int start) {
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans ^= start + 2 * i;
    }
    return ans;
  }
}

```

### Python

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

```

### CPP

```cpp
class Solution {
public:
  int xorOperation(int n, int start) {
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans ^= start + 2 * i;
    }
    return ans;
  }
};

```