Two Unpaired Tickets

MediumBit Manipulation

Problem

A cloakroom issues paired tickets: the customer and the coat each get a copy with the same number. At closing time all ticket stubs are dumped into stubs. Every number appears exactly twice, except two numbers whose second copy was lost; those two appear exactly once.

Return the two unpaired numbers in ascending order, using O(n) time and O(1) extra memory.

Example 1

Input:
stubs = [1, 2, 1, 3, 2, 5]
Output:
[3, 5]

1 and 2 are paired; 3 and 5 are not.

Example 2

Input:
stubs = [9, 4]
Output:
[4, 9]

Example 3

Input:
stubs = [0, 7, 7, 1]
Output:
[0, 1]

Constraints

  • 2 ≤ stubs.length ≤ 3 · 10^4
  • 0 ≤ stubs[i] < 2^31
  • Exactly two distinct values appear once; every other value appears exactly twice.

Hint

Show the first hint

XOR of everything cancels the pairs. What is left?

Walkthrough

How to approach it

01Clarify before coding

  • Can the two unpaired numbers be equal? No, they are distinct, so their XOR is non-zero.
  • In what order do I return them? Ascending, so the answer is unique.
  • Can 0 be one of them? Yes; nothing in the method relies on non-zero values.

02Brute force

Count occurrences in a hash map and collect the values seen once, then sort the two.

Cost: O(n) time but O(n) extra memory, which breaks the constraint.

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.