XOR Operation in an Array: Bit Manipulation Basics
LeetCode XOR Operation in an Array (Problem 1486) asks: given an integer n and an integer start, define an array nums where nums[i] = start + 2 * i for 0 <= i < n. Return the bitwise XOR of all elements of nums.
For example, when n = 5 and start = 0, the array is [0, 2, 4, 6, 8] and the XOR of all elements is 8.
Why this problem matters
XOR is one of the most useful bitwise operations in programming. It has several properties that show up repeatedly in interview problems: XOR-ing a number with itself produces 0, XOR-ing with 0 returns the original number, and XOR is both commutative and associative. This problem gives you a simple context to practice the core XOR accumulation pattern, which forms the foundation for harder problems like finding a single non-duplicate element or computing prefix XOR queries.
The key insight
You do not need to build the array at all. Since you are just computing the XOR of every element, you can iterate from 0 to n - 1, compute start + 2 * i on the fly, and XOR it into a running result. This avoids allocating any extra memory for the array.
The solution
def xor_operation(n: int, start: int) -> int:
result = 0
for i in range(n):
result ^= start + 2 * i
return result
The variable result starts at 0. On each iteration, you compute the next element of the array (start + 2 * i) and XOR it into result. After all n iterations, result holds the XOR of the entire array. Starting at 0 works because XOR-ing any value with 0 returns that value unchanged, so the first iteration effectively sets result to the first element.
XOR has three properties worth memorizing: a ^ a = 0 (self-cancellation), a ^ 0 = a (identity), and a ^ b = b ^ a (commutativity). These three rules unlock a wide range of bit manipulation problems.
Visual walkthrough
Step 1: XOR the first two elements
0 XOR 2 = 2. Bits that differ become 1, bits that match stay 0.
Step 2: XOR running result with next element
2 XOR 4 = 6. Each bit position is compared independently.
Step 3: Continue XOR accumulation
6 XOR 6 = 0. XOR-ing a number with itself always produces 0.
Step 4: Final XOR gives the answer
0 XOR 8 = 8. XOR-ing with 0 returns the other value unchanged. Final answer: 8.
Each step XORs the running result with the next array element. Notice how Step 3 produces 0 because 6 ^ 6 = 0, a direct application of the self-cancellation property. Then Step 4 XORs 0 with 8, giving the final answer of 8 via the identity property.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Direct XOR | O(n) | O(1) |
You iterate through n elements exactly once, performing a constant-time XOR at each step. No extra data structures are needed since you accumulate the result in a single integer variable.
The building blocks
1. XOR accumulation pattern
result = 0
for value in values:
result ^= value
This is the workhorse pattern for combining a collection of values with XOR. You initialize an accumulator to 0 (the XOR identity) and fold each element in. This same pattern appears in problems like Single Number, where XOR cancellation reveals the unpaired element.
2. Arithmetic sequence generation
for i in range(n):
element = start + 2 * i
The array follows an arithmetic sequence with a common difference of 2. Rather than building the sequence into a list, you generate each term on the fly using the formula. This is a general technique: whenever a problem defines an array by a formula, you can often skip the allocation and compute values inline.
Edge cases
n = 1. The array contains only [start]. The XOR of a single element is that element itself. The loop runs once, XOR-ing start with the initial 0, so the result is start.
start = 0. The array is [0, 2, 4, ...]. XOR-ing with 0 on the first iteration has no effect, so the result is driven entirely by the remaining elements.
All elements cancel. If elements happen to pair up and cancel via XOR (like 6 ^ 6 = 0 in our example), the intermediate result drops to 0 before picking up the remaining elements. The algorithm handles this naturally.
From understanding to recall
The XOR accumulation pattern is simple to understand, but in a timed interview you need it to be automatic. You should not have to pause and think about why the accumulator starts at 0 or how XOR folds across a sequence. Spaced repetition makes this second nature. You write the pattern from scratch today, revisit it in a few days, then again next week. Each repetition strengthens recall until the pattern surfaces instantly when you see a problem that calls for it.
Related posts
- Single Number - The classic XOR cancellation problem
- XOR Queries of a Subarray - Prefix XOR technique
- Counting Bits - Another bit manipulation fundamental
CodeBricks breaks problems like this into their reusable building blocks and drills them with spaced repetition. Instead of memorizing solutions, you learn the patterns that transfer across hundreds of problems.