XOR Operation in an Array

Easy
425.

XOR Operation in an Array

XOR Operation in an Array is an easy coding problem on math, bit manipulation and simulation, asked in Amazon and Adobe interviews.

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 <= 50
  • 0 <= start <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} start
 * @return {number}
 */
var xorOperation = function(n, start) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 50
  • 0 <= start <= 1000

Hints for XOR Operation in an Array

  1. Hint 1

    The array is never actually needed — generate the values on the fly.

  2. Hint 2

    XOR them into a running accumulator initialised to 0.

  3. 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

  1. out = 0; for i in 0..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 out

Java

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