XOR Operation in an Array
Problem
You are given two integers n and start. Define an array nums of length n where nums[i] = start + 2*i for each index i from 0 to n-1. Return the bitwise XOR of every element in nums.
n = 5, start = 08def xor_operation(n, start):
acc = 0
for i in range(n):
acc ^= start + 2 * i
return accfunction xorOperation(n, start) {
let acc = 0;
for (let i = 0; i < n; i++) {
acc ^= start + 2 * i;
}
return acc;
}class Solution {
public int xorOperation(int n, int start) {
int acc = 0;
for (int i = 0; i < n; i++) {
acc ^= start + 2 * i;
}
return acc;
}
}int xorOperation(int n, int start) {
int acc = 0;
for (int i = 0; i < n; i++) {
acc ^= start + 2 * i;
}
return acc;
}Explanation
The array is never actually given to us — it is described by a formula. Each element is nums[i] = start + 2*i, so the values form an arithmetic sequence that steps up by 2: start, start + 2, start + 4, and so on.
We do not need to build the array at all. We keep a running accumulator acc starting at 0 and fold each generated value into it with acc ^= start + 2*i. XOR is associative and order-independent, so combining the terms one at a time gives the same result as XOR-ing the whole array.
Recall the two handy XOR facts: x ^ 0 = x (zero is the identity) and x ^ x = 0 (a value cancels its twin). Starting from 0 means the first term simply lands in acc unchanged, then each later term mixes in.
Example: n = 5, start = 0 generates [0, 2, 4, 6, 8]. Walking through it: 0 ^ 2 = 2, 2 ^ 4 = 6, 6 ^ 6 = 0, 0 ^ 8 = 8. The answer is 8.
This direct loop runs in linear time. There is also a clever O(1) closed form: since all elements share the same lowest bit, you can factor out 2 and reuse the prefix-XOR of consecutive integers 0..n-1, but the straightforward loop is already plenty fast for the small bounds here.