Skip to main content
Talentd

XOR Operation in an Array - Solution & Explanation

EasyMathBit Manipulation12 min readAsked at: Google, Walmart Labs
Practice this problem

Problem Statement

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 <= 1000
  • 0 <= start <= 1000
  • n == nums.length

Approach Overview

Problem Overview: You are given two integers n and start. Construct a virtual array where nums[i] = start + 2 * i for 0 ≤ i < n. The task is to compute the XOR of all elements in this array without explicitly storing unnecessary data.

Approach 1: Iterative Calculation with XOR Accumulation (O(n) time, O(1) space)

The most direct approach is to simulate the array values and accumulate their XOR. Start with a variable result = 0. Iterate from i = 0 to n - 1, compute the value start + 2 * i, and XOR it with the running result using result ^= value. XOR works well here because it is associative and commutative, meaning order does not affect the result. This solution avoids building the array explicitly and instead computes each element on the fly. The time complexity is O(n) because you process each element once, while the space complexity remains O(1). This method relies on basic bit manipulation operations and is typically the first solution developers implement.

Approach 2: Mathematical Pattern Using XOR Properties (O(1) time, O(1) space)

The array values follow a strict arithmetic pattern: every element increases by 2. This structure allows a mathematical shortcut using known patterns of XOR from 0 to x. The key insight is to rewrite the expression so the sequence becomes a shifted XOR range. By factoring out the multiplication by 2 and analyzing the parity of the starting value, the computation can be reduced to evaluating XOR prefixes using the formula for xor(0..k), which repeats every four numbers. Instead of iterating through n elements, you compute a few constant-time expressions based on these patterns. The result is an O(1) time and O(1) space solution. This technique demonstrates how understanding numeric patterns and math properties can remove the need for iteration.

Recommended for interviews: Start with the iterative XOR accumulation. It clearly shows you understand how the array is constructed and how XOR works. Once that is correct, discuss the mathematical optimization. Interviewers often appreciate the transition from a straightforward O(n) implementation to the constant-time solution because it demonstrates deeper reasoning about XOR patterns and arithmetic sequences.

Approach 1: Iterative Calculation with XOR Accumulation

This approach involves iterating over the indices from 0 to n-1, calculating the value of each element 'nums[i]' using the formula 'start + 2 * i', and accumulating the result using a XOR operation.

The function xorOperation takes in two integers, n and start. It initializes a variable xor_result to zero and iterates over each index, computing start + 2 * i for each index and XORing it with xor_result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Mathematical Pattern Calculation using XOR Properties

Using the properties of XOR, we can leverage the repetitive pattern in binary and arithmetic operations to calculate the XOR without iterating explicitly to form the array.

XOR of numbers follows a predictable pattern, often used in finding results efficiently in number sequences by leveraging prefix XOR calculations.

This solution leverages XOR properties that dictate how sequences of numbers behave, avoiding explicit iterations.

The helper function computes XOR from 0 to a given number, used to get the XOR up to start + 2 * n - 2 and subtracts those lesser to form.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1), Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Simulation

We can directly simulate to calculate the XOR result of all elements in the array.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Calculation with XOR Accumulation

Time Complexity: O(n), Space Complexity: O(1)

Mathematical Pattern Calculation using XOR Properties

Time Complexity: O(1), Space Complexity: O(1)

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Calculation with XOR AccumulationO(n)O(1)Best for clarity and interviews when deriving the mathematical pattern is unnecessary
Mathematical Pattern Using XOR PropertiesO(1)O(1)Optimal solution when you recognize XOR prefix patterns and want constant-time computation

Video Solution

XOR of numbers in a range [L, R] | XOR operation in an array (LeetCode 1486) | Innovative • Nikhil Lohia • 1,312 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is XOR Operation in an Array easy or hard?
XOR Operation in an Array is classified as an Easy problem with a high acceptance rate around 87%. The iterative solution is straightforward, but recognizing the XOR mathematical pattern for the O(1) optimization adds an extra layer of insight.
XOR Operation in an Array Python/Java solution
In both Python and Java, the typical solution loops from 0 to n-1, computes start + 2*i, and applies the XOR operator to a running result. Python uses the ^ operator, and Java uses the same ^ bitwise XOR operator. The logic is identical across languages.
How to solve XOR Operation in an Array in O(n)?
Initialize a variable result = 0 and iterate from i = 0 to n - 1. For each iteration compute value = start + 2 * i and update result ^= value. After the loop finishes, result contains the XOR of all generated elements. This approach runs in O(n) time and O(1) space.
What is the best approach for XOR Operation in an Array?
The most efficient approach uses XOR mathematical patterns to compute the result in O(1) time and O(1) space. By transforming the sequence nums[i] = start + 2*i and applying the repeating pattern of XOR from 0 to n, the entire result can be calculated with constant-time formulas instead of iteration.
Is XOR Operation in an Array asked at Google/Amazon/Meta?
Problems involving XOR patterns and bit manipulation appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem is considered easy, it tests understanding of XOR behavior and arithmetic sequences, which often appear in harder variations.
What data structure is used in XOR Operation in an Array?
No complex data structure is required. The problem relies primarily on bitwise XOR operations and simple arithmetic. The solution maintains a single integer accumulator, making it a pure bit manipulation and math problem rather than a data structure problem.
What is the time complexity of XOR Operation in an Array?
The straightforward solution runs in O(n) time by iterating from 0 to n-1 and XORing each computed value. An optimized mathematical approach reduces the time complexity to O(1) using XOR prefix patterns and arithmetic properties of the sequence.

Ready to solve this problem?

Practice XOR Operation in an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer