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 Sam K., 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

More Bit Manipulation practice problems

See all Bit Manipulation problems →