Unchain the XOR Log

EasyArrays & Hashing

Problem

A device stores a sequence of non-negative readings arr compactly: it keeps only the first reading first and an array links where links[i] = arr[i] XOR arr[i + 1].

Given links and first, reconstruct and return the full sequence arr (its length is links.length + 1).

Example 1

Input:
links = [1, 2, 3], first = 1
Output:
[1, 0, 2, 1]

1 XOR 0 = 1, 0 XOR 2 = 2, 2 XOR 1 = 3, matching links.

Example 2

Input:
links = [6, 2, 7, 3], first = 4
Output:
[4, 2, 0, 7, 4]

Constraints

  • 0 ≤ links.length ≤ 10^4
  • 0 ≤ links[i], first ≤ 10^5

Hint

Show the first hint

If you know arr[i] and links[i], can you solve links[i] = arr[i] XOR arr[i + 1] for arr[i + 1]?

Walkthrough

How to approach it

01Clarify before coding

  • Is the first reading always given? Yes; without it the sequence is not unique.
  • Can links be empty? Yes: the answer is just [first].
  • Are values non-negative? Yes, so bitwise XOR behaves the same in every language.

02Brute force

For each next position, try every candidate value c and keep the one with arr[i] XOR c == links[i].

Cost: O(n · V) with V up to 10^5 candidates per position: wasteful when the equation can be solved directly.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.