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 <= 10000 <= start <= 1000n == nums.lengthProblem Overview: You are given two integers n and start. Construct a virtual array where nums[i] = start + 2 * i for 0 ≤ i < n. The task is to compute the XOR of all elements in this array without explicitly storing unnecessary data.
Approach 1: Iterative Calculation with XOR Accumulation (O(n) time, O(1) space)
The most direct approach is to simulate the array values and accumulate their XOR. Start with a variable result = 0. Iterate from i = 0 to n - 1, compute the value start + 2 * i, and XOR it with the running result using result ^= value. XOR works well here because it is associative and commutative, meaning order does not affect the result. This solution avoids building the array explicitly and instead computes each element on the fly. The time complexity is O(n) because you process each element once, while the space complexity remains O(1). This method relies on basic bit manipulation operations and is typically the first solution developers implement.
Approach 2: Mathematical Pattern Using XOR Properties (O(1) time, O(1) space)
The array values follow a strict arithmetic pattern: every element increases by 2. This structure allows a mathematical shortcut using known patterns of XOR from 0 to x. The key insight is to rewrite the expression so the sequence becomes a shifted XOR range. By factoring out the multiplication by 2 and analyzing the parity of the starting value, the computation can be reduced to evaluating XOR prefixes using the formula for xor(0..k), which repeats every four numbers. Instead of iterating through n elements, you compute a few constant-time expressions based on these patterns. The result is an O(1) time and O(1) space solution. This technique demonstrates how understanding numeric patterns and math properties can remove the need for iteration.
Recommended for interviews: Start with the iterative XOR accumulation. It clearly shows you understand how the array is constructed and how XOR works. Once that is correct, discuss the mathematical optimization. Interviewers often appreciate the transition from a straightforward O(n) implementation to the constant-time solution because it demonstrates deeper reasoning about XOR patterns and arithmetic sequences.
This approach involves iterating over the indices from 0 to n-1, calculating the value of each element 'nums[i]' using the formula 'start + 2 * i', and accumulating the result using a XOR operation.
The function xorOperation takes in two integers, n and start. It initializes a variable xor_result to zero and iterates over each index, computing start + 2 * i for each index and XORing it with xor_result.
Time Complexity: O(n), Space Complexity: O(1)
Using the properties of XOR, we can leverage the repetitive pattern in binary and arithmetic operations to calculate the XOR without iterating explicitly to form the array.
XOR of numbers follows a predictable pattern, often used in finding results efficiently in number sequences by leveraging prefix XOR calculations.
This solution leverages XOR properties that dictate how sequences of numbers behave, avoiding explicit iterations.
The helper function computes XOR from 0 to a given number, used to get the XOR up to start + 2 * n - 2 and subtracts those lesser to form.
Time Complexity: O(1), Space Complexity: O(1)
We can directly simulate to calculate the XOR result of all elements in the array.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Calculation with XOR Accumulation | Time Complexity: O(n), Space Complexity: O(1) |
| Mathematical Pattern Calculation using XOR Properties | Time Complexity: O(1), Space Complexity: O(1) |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Calculation with XOR Accumulation | O(n) | O(1) | Best for clarity and interviews when deriving the mathematical pattern is unnecessary |
| Mathematical Pattern Using XOR Properties | O(1) | O(1) | Optimal solution when you recognize XOR prefix patterns and want constant-time computation |
LeetCode#1486) XOR Operation in an Array • Tech Videos • 1,221 views views
Watch 9 more video solutions →Practice XOR Operation in an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor