Log inSign up
easyGeeksforGeeksNot Started

XOR of All Numbers in an Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of integers nums, compute and return the bitwise XOR of all elements in the array.

Formally, compute nums[0] ^ nums[1] ^ ... ^ nums[n - 1].

Example 1 · Example 1: Four Elements:

Input: nums = [2, 4, 7, 5]
Output: 4
Explanation: 2 ^ 4 = 6. 6 ^ 7 = 1. 1 ^ 5 = 4.

Example 2 · Example 2: All Identical Elements:

Input: nums = [3, 3, 3]
Output: 3
Explanation: 3 ^ 3 ^ 3 = 0 ^ 3 = 3.

Example 3 · Example 3: Pair Cancellation:

Input: nums = [1, 2, 1, 2]
Output: 0
Explanation: (1 ^ 1) ^ (2 ^ 2) = 0 ^ 0 = 0.

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand XOR as an algebraic group operation.
  • Explore instruction-level parallelism through 4-way accumulator unrolling.
  • Implement robust solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Compute cumulative XOR over a dataset.
  • Parity check of entire array.
  • Reduction primitive for range queries.

Algorithmic Decision Tree:

  • Initialize res = 0.
  • Accumulate res ^= nums[i] for all elements.

Connected Patterns:

Single NumberXOR Queries of a SubarraySubsets XOR Sum

1. Standard Sequential Loop

Intuition

Initialize res = 0. For each element x in nums, compute res ^= x. Return res.

When to apply: Basic standard implementation.

Algorithm

  1. Step 1: Set res = 0.
  2. Step 2: Loop x in nums: res ^= x.
  3. Step 3: Return res.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int getXorSumSequential(const vector<int>& nums) {
7 int res = 0;
8 for (int x : nums) {
9 res ^= x;
10 }
11 return res;
12}
13
14int main() {
15 vector<int> nums = {2, 4, 7, 5};
16 cout << "Sequential: " << getXorSumSequential(nums) << endl; // 4
17 return 0;
18}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

2. Divide and Conquer (Recursive XOR)

Intuition

Define solve(l, r). If l == r, return nums[l]. Split into mid = l + (r - l) / 2. Return solve(l, mid) ^ solve(mid + 1, r).

When to apply: When modeling parallel reduction across cores.

Algorithm

  1. Step 1: If l == r, return nums[l].
  2. Step 2: mid = (l + r) / 2.
  3. Step 3: Return solve(l, mid) ^ solve(mid + 1, r).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int dnc(const vector<int>& nums, int l, int r) {
7 if (l == r) return nums[l];
8 int mid = l + (r - l) / 2;
9 return dnc(nums, l, mid) ^ dnc(nums, mid + 1, r);
10}
11
12int getXorSumDnC(const vector<int>& nums) {
13 if (nums.empty()) return 0;
14 return dnc(nums, 0, nums.size() - 1);
15}
16
17int main() {
18 vector<int> nums = {2, 4, 7, 5};
19 cout << "DnC: " << getXorSumDnC(nums) << endl; // 4
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(log n) call stack

3. 4-Way Loop Unrolling (Instruction-Level Parallelism)

Intuition

Maintain four independent accumulators: x0, x1, x2, and x3. In the main loop, advance by 4 elements each step, XORing one element into each accumulator. Finally, XOR x0 ^ x1 ^ x2 ^ x3 along with any leftover tail elements.

When to apply: High-throughput performance engineering for large arrays.

Algorithm

  1. Step 1: Initialize x0 = 0, x1 = 0, x2 = 0, x3 = 0, i = 0.
  2. Step 2: Loop while i + 3 < n: x0 ^= nums[i], x1 ^= nums[i+1], x2 ^= nums[i+2], x3 ^= nums[i+3], i += 4.
  3. Step 3: Combine res = x0 ^ x1 ^ x2 ^ x3.
  4. Step 4: Process remaining tail elements while i < n: res ^= nums[i], i++.
  5. Step 5: Return res.

Sequential XOR Trace: nums = [2, 4, 7, 5]

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Step 1: res = 0 ^ 2 = 2
Visual state
Values and pointers at this exact step
pointers
S
2
0
↑ res = 2
Check / comparison
res = 2
Decision / next transition
nums[0] processed.
Why this step matters

Step 1: res = 0 ^ 2 = 2.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int getXorSum(vector<int>& nums) {
9 int x0 = 0, x1 = 0, x2 = 0, x3 = 0;
10 int n = nums.size();
11 int i = 0;
12
13 for (; i + 3 < n; i += 4) {
14 x0 ^= nums[i];
15 x1 ^= nums[i + 1];
16 x2 ^= nums[i + 2];
17 x3 ^= nums[i + 3];
18 }
19
20 int res = x0 ^ x1 ^ x2 ^ x3;
21 for (; i < n; ++i) {
22 res ^= nums[i];
23 }
24 return res;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> nums = {2, 4, 7, 5};
31 cout << "Optimal Unrolled: " << sol.getXorSum(nums) << endl; // 4
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Standard Sequential IterationO(n)O(1)Loop through array sequentially: res ^= nums[i].Linear scan.
2.Better — Divide and Conquer (Recursive)O(n)O(log n) call stackDivide array into left and right halves, recursively XOR halves, and XOR their results.Function call frames.
3.Optimal — 4-Way Loop UnrollingOptimalO(n)O(1)Accumulate into 4 separate independent registers to maximize instruction-level parallelism, then XOR them together.Memory bandwidth.

Common Pitfalls & Crucial Edge Cases

Initializing accumulator to 1 instead of 0

Must initialize xorSum = 0.

Assuming result is always positive

XOR sum of negative numbers can be negative in two's complement.

Sorting the array first

Sorting takes unnecessary O(n log n) time; XOR is associative so order does not matter.

Crucial Edge Cases to Validate:

  • Empty array `[]` — Returns 0.
  • Single element `[x]` — Returns x.
  • Array of identical elements `[x, x, ..., x]` — If length is even returns 0; if odd returns x.
  • Array contains 0s — 0 ^ x = x, so zeros have no effect.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that XOR order invariance (commutativity & associativity) means elements can be processed in any sequence.
  2. Discuss the 1-to-N modulo 4 shortcut as a useful building block for range XOR problems.
  3. Emphasize the zero memory allocation overhead.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the result of XORing an entire array of n numbers?

2.What is the time complexity to compute the XOR sum of an array of n numbers?

3.What identity allows constant time XOR calculation of all numbers from 1 to N?

Back to DSA Sheet