XOR Operation in an Array — Solution in Python, Java & C++
XOR Operation in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
XOR Operation in an Array is an easy coding problem on math, bit manipulation and simulation, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Math, Bit Manipulation, Simulation
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given integers n and start. Define an array nums of length n by nums[i] = start + 2 * i.
Return the bitwise XOR of every element of nums.
Example 1
Input: n = 5, start = 0
Output: 8
Explanation: The array is [0,2,4,6,8].
Example 2
Input: n = 4, start = 3
Output: 8
Example 3
Input: n = 1, start = 7
Output: 7
Constraints
1 <= n <= 500 <= start <= 1000
Hints for XOR Operation in an Array
Hint 1
The array is never actually needed — generate the values on the fly.
Hint 2
XOR them into a running accumulator initialised to 0.
Hint 3
The closed form uses the fact that all the terms share the same lowest bit.
How to solve XOR Operation in an Array
Generate start + 2i on the fly and XOR into an accumulator.
Approach
out = 0; foriin0..n-1,out ^= start + 2i.
Why it works
The array is defined by a closed form, so it need not be materialised.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- An O(1) closed form exists via XOR of a prefix of integers, but is not required.
Reference solution
Python
def xorOperation(n: int, start: int) -> int:
out = 0
for i in range(n):
out ^= start + 2 * i
return outJava
public static int xorOperation(int n, int start) {
int out = 0;
for (int i = 0; i < n; i++) out ^= start + 2 * i;
return out;
}C++
int xorOperation(int n, int start) {
int out = 0;
for (int i = 0; i < n; i++) out ^= start + 2 * i;
return out;
}JavaScript
var xorOperation = function(n, start) {
let out = 0;
for (let i = 0; i < n; i++) out ^= start + 2 * i;
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Bit Manipulation