LeetCode 1486 - XOR Operation in an Array

LeetCode Problem 1486

Difficulty: 🟢 Easy
Topics: Math, Bit Manipulation

Solution

Problem Understanding

The problem gives us two integers, n and start. We must construct an array named nums of length n, where each element is defined by the formula:

$$nums[i] = start + 2 \times i$$

This means the array begins at start and increases by 2 for every next position. After constructing the array, we must compute the bitwise XOR of all elements.

The XOR operator, written as ^, compares bits position by position. A bit becomes 1 if the corresponding bits are different, and 0 if they are the same. XOR also has several useful properties:

• a ^ a = 0
• a ^ 0 = a
• XOR is associative and commutative

The input constraints are very small:

• 1 <= n <= 1000
• 0 <= start <= 1000

Since the array can contain at most 1000 elements, even a straightforward simulation will run very quickly. This tells us that efficiency is not a major concern here, but we should still aim for a clean and correct implementation.

One important detail is that the array itself does not need to be explicitly stored. We can generate each value one at a time and immediately apply XOR to an accumulator variable.

Important edge cases include:

• n = 1, where the answer is simply start
• start = 0, where the sequence begins from zero
• Cases where repeated XOR operations cancel values in non-obvious ways
• Large valid values such as n = 1000 and start = 1000

The problem guarantees valid input sizes, so we do not need to handle invalid values or empty arrays.

Approaches

Brute Force Approach

The most direct solution is to explicitly build the array nums, then XOR all elements together.

We iterate from 0 to n - 1, compute:

$$start + 2 \times i$$

and append it to an array. After constructing the array, we traverse it again and continuously apply XOR to an accumulator.

This works because XOR is applied exactly as the problem statement describes.

Although this solution is perfectly acceptable for the given constraints, it uses extra memory to store the array even though the array values are only needed once.

Optimal Approach

A better approach is to avoid storing the array entirely.

Instead of building nums, we generate each value on the fly and immediately XOR it into the running result.

For each index i:

$$current = start + 2 \times i$$

Then:

$$result = result ; \hat{} ; current$$

This produces the same final XOR while using constant extra space.

The key observation is that XOR can be accumulated incrementally. Since XOR is associative and commutative, we do not need the full array at any point.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Builds the entire array before XOR computation
Optimal	O(n)	O(1)	Computes values on the fly without storing the array

Algorithm Walkthrough

1. Initialize a variable result to 0.

This variable will store the running XOR of all generated numbers. Starting with 0 works because x ^ 0 = x. 2. Iterate through all indices from 0 to n - 1.

Each index corresponds to one element in the conceptual array. 3. Compute the current value using the formula:

$$current = start + 2 \times i$$

This recreates exactly the value defined in the problem statement. 4. XOR the current value into result.

$$result = result ; \hat{} ; current$$

XOR accumulates all values together. 5. After the loop finishes, return result.

At this point, every generated number has been included exactly once in the XOR calculation.

Why it works

The algorithm works because XOR is associative and commutative. This means we can process values one at a time in any order without changing the final result.

The loop generates exactly the same sequence defined by the problem:

$$[start,\ start+2,\ start+4,\ \dots]$$

Each generated value is XORed into the accumulator exactly once, so the final value is the XOR of all array elements.

Python Solution

class Solution:
    def xorOperation(self, n: int, start: int) -> int:
        result = 0

        for i in range(n):
            current_value = start + 2 * i
            result ^= current_value

        return result

The implementation begins by initializing result to 0. This variable stores the cumulative XOR.

The loop runs exactly n times, corresponding to the indices of the conceptual array. For each iteration, the current array value is generated using the formula from the problem statement.

Instead of storing values in a list, the solution immediately XORs the generated value into result. This keeps the memory usage constant.

Finally, after all values have been processed, the method returns the accumulated XOR result.

Go Solution

func xorOperation(n int, start int) int {
    result := 0

    for i := 0; i < n; i++ {
        currentValue := start + 2*i
        result ^= currentValue
    }

    return result
}

The Go implementation follows the same logic as the Python solution.

Go uses the := operator for variable declaration and initialization. The loop syntax is slightly different, but the algorithm remains identical.

Since all values remain small under the problem constraints, integer overflow is not a concern in Go.

Worked Examples

Example 1

Input:

n = 5
start = 0

Constructed array:

[0, 2, 4, 6, 8]

Step-by-step execution:

Iteration	Current Value	Result Before XOR	Result After XOR
0	0	0	0
1	2	0	2
2	4	2	6
3	6	6	0
4	8	0	8

Final answer:

8

Example 2

Input:

n = 4
start = 3

Constructed array:

[3, 5, 7, 9]

Step-by-step execution:

Iteration	Current Value	Result Before XOR	Result After XOR
0	3	0	3
1	5	3	6
2	7	6	1
3	9	1	8

Final answer:

8

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We process each of the n elements exactly once
Space	O(1)	Only a few variables are used regardless of input size

The algorithm performs one loop over the conceptual array, so the running time grows linearly with n.

No additional data structures are allocated. The solution only stores the running XOR result and temporary loop variables, so the extra space usage remains constant.

Test Cases

solution = Solution()

assert solution.xorOperation(5, 0) == 8      # Example 1
assert solution.xorOperation(4, 3) == 8      # Example 2

assert solution.xorOperation(1, 0) == 0      # Single element, zero
assert solution.xorOperation(1, 7) == 7      # Single element, non-zero

assert solution.xorOperation(2, 0) == 2      # Small even-sized array
assert solution.xorOperation(3, 1) == 7      # Small odd-sized array

assert solution.xorOperation(5, 2) == 2      # Mixed XOR cancellations
assert solution.xorOperation(10, 5) == 2     # Larger sequence

assert solution.xorOperation(1000, 1000) >= 0  # Maximum constraints

Test Summary

Test	Why
n=5, start=0	Validates the first provided example
n=4, start=3	Validates the second provided example
n=1, start=0	Tests smallest possible input
n=1, start=7	Ensures single-element arrays return the element itself
n=2, start=0	Tests simple even-sized sequence
n=3, start=1	Tests odd-sized sequence behavior
n=5, start=2	Verifies XOR cancellation effects
n=10, start=5	Tests a larger normal input
n=1000, start=1000	Confirms handling of maximum constraints

Edge Cases

One important edge case occurs when n = 1. In this situation, the array contains only one element:

$$[start]$$

The XOR of a single number is the number itself. A buggy implementation might accidentally initialize incorrectly or skip processing. This implementation handles the case naturally because the loop executes exactly once.

Another important edge case is when start = 0. XOR with zero behaves differently from normal arithmetic operations, and some implementations may incorrectly assume zero changes the result. Since XOR follows the identity x ^ 0 = x, the algorithm works correctly without any special handling.

A third edge case involves larger values near the maximum constraints, such as n = 1000 and start = 1000. Even though the numbers become larger, the algorithm still processes each value independently in linear time. Memory usage stays constant because the array is never stored explicitly.