XOR Operation in an Array
EasyPrompt
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.length
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Define a helper function
prefixXor(x)that computes0 ^ 1 ^ ... ^ xin O(1). - Calculate
s = start >> 1. - Calculate the XOR sum of the range
[s, s + n - 1]asrangeXor = 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.
Walkthrough
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:
-
The Least Significant Bit (LSB): The LSB of each term
2*(s+i) + eis simplye. We are XORingewith itselfntimes. The result iseifnis odd, and0ifnis even. This can be calculated as(n & 1) & e, or(n & 1) & (start & 1). -
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.