Skip to main content

1486. XOR Operation in an Array

easy

Compute the XOR of an arithmetic sequence nums[i] = start + 2*i for i in [0, n). Naïve loop is fine for the small bound; the closed-form is the bonus brainteaser.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= n <= 1000
  • 0 <= start <= 1000
  • n == nums.length

Examples

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.

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

n <= 1000 is tiny — a straightforward loop is correct and fast.

Hint 2

For style: every nums[i] shares its lowest bit with start (since 2*i is even). Factor out that bit and reduce to XOR of i for i in [start/2, start/2 + n).

Hint 3

Use the well-known pattern XOR(0..k): {k, 1, k+1, 0} cycling on k mod 4.

Solution approach

Reveal approach

Direct loop is the recommended baseline. result = 0; for i in range(n): result ^= (start + 2 * i); return result. O(n) time, O(1) space — and n <= 1000 makes this trivial. For the closed-form: factor nums[i] = 2 * (start/2 + i) + (start & 1). The lowest bit contributes n * (start & 1) parity = (n & 1) * (start & 1) to the answer. The remaining XOR is 2 * (XOR over i in [start/2, start/2 + n) of i), which uses the cycle XOR(0..k) = {k, 1, k+1, 0} for k mod 4 == {0, 1, 2, 3}. Combine with shift. Constant-time but error-prone; the loop is what to write in an interview.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • bit-manipulation
  • xor
  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill XOR Operation in an Array and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →