XOR Operation in an Array

EASY

Description

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

Approaches

Checkout 2 different approaches to solve XOR Operation in an Array. Click on different approaches to view the approach and algorithm in detail.

Constant Time Mathematical Approach

A more advanced approach involves mathematical and bitwise manipulation to compute the result in constant time, O(1). This method avoids iteration by analyzing the properties of the XOR operation on an arithmetic progression.

Algorithm

Define a helper function prefixXor(x) that computes 0 ^ 1 ^ ... ^ x in O(1).
Calculate s = start >> 1.
Calculate the XOR sum of the range [s, s + n - 1] as rangeXor = prefixXor(s - 1) ^ prefixXor(s + n - 1).
The contribution from the higher bits is higherBits = rangeXor << 1.
The contribution from the least significant bit is lsb = (n & 1) & (start & 1).
The final result is higherBits | lsb.

The core idea is to decompose the problem by looking at the bits. Each number in the sequence is start + 2*i. Let's analyze the structure of these numbers. Let s = start >> 1 and e = start & 1. Then start = 2*s + e. The i-th term is 2*s + e + 2*i = 2*(s+i) + e.

The final XOR sum can be broken down into two parts:

The Least Significant Bit (LSB): The LSB of each term 2*(s+i) + e is simply e. We are XORing e with itself n times. The result is e if n is odd, and 0 if n is even. This can be calculated as (n & 1) & e, or (n & 1) & (start & 1).
The Higher Bits: The higher bits of the XOR sum come from the 2*(s+i) parts. The XOR sum of these is (2*s) ^ (2*(s+1)) ^ ... ^ (2*(s+n-1)). Using the property (a << 1) ^ (b << 1) = (a ^ b) << 1, this simplifies to (s ^ (s+1) ^ ... ^ (s+n-1)) << 1.

The sum s ^ (s+1) ^ ... ^ (s+n-1) is an XOR sum of a contiguous range of integers. This can be computed efficiently using a helper function, prefixXor(x), which calculates 0 ^ 1 ^ ... ^ x. The XOR sum of a range [a, b] is prefixXor(b) ^ prefixXor(a-1). The prefixXor(x) function itself can be implemented in O(1) time based on the value of x % 4.

By combining the results from the LSB and the higher bits, we can find the final answer in constant time.

class Solution {
    // Helper function to compute 0^1^...^x in O(1)
    private int prefixXor(int x) {
        if (x < 0) {
            return 0;
        }
        switch (x % 4) {
            case 0: return x;
            case 1: return 1;
            case 2: return x + 1;
            case 3: return 0;
        }
        return 0; // Should not be reached
    }

    public int xorOperation(int n, int start) {
        int s = start >> 1;
        int e = start & 1;

        // XOR sum of s, s+1, ..., s+n-1
        int rangeXor = prefixXor(s - 1) ^ prefixXor(s + n - 1);
        
        // Higher bits part
        int higherBits = rangeXor << 1;
        
        // LSB part
        int lsb = (n & 1) & e;
        
        return higherBits | lsb;
    }
}

Complexity Analysis

Time Complexity: O(1) - The solution involves a fixed number of arithmetic and bitwise operations, regardless of the value of `n`.Space Complexity: O(1) - Only a few variables are used for calculations.

Pros and Cons

Pros:

Extremely efficient, providing a constant time solution.
Demonstrates a deep understanding of bitwise operations and mathematical patterns.

Cons:

The logic is significantly more complex to derive and understand.
Might be considered overkill given the small constraints of the problem.

Code Solutions

Checking out 3 solutions in different languages for XOR Operation in an Array. Click on different languages to view the code.

class Solution {
public
  int xorOperation(int n, int start) {
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans ^= start + 2 * i;
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for XOR Operation in an Array

Patterns:

MathBit Manipulation