Survivor of the Triples

MediumBit Manipulation

Problem

A triple-redundant flight computer writes every telemetry value three times. One value was written only once before a reset. The log values holds signed 32-bit integers.

Return the value that appears exactly once. Every other value appears exactly three times. Use O(n) time and O(1) extra memory.

Example 1

Input:
values = [2, 2, 3, 2]
Output:
3

Example 2

Input:
values = [0, 1, 0, 1, 0, 1, 99]
Output:
99

Example 3

Input:
values = [-2, -2, -2, -7]
Output:
-7

Negative numbers use their 32-bit two's-complement form.

Constraints

  • 1 ≤ values.length ≤ 3 · 10^4
  • -2^31 ≤ values[i] < 2^31
  • Exactly one value appears once; every other value appears exactly three times.

Hint

Show the first hint

XOR no longer works: three copies of x XOR to x. Look at one bit position at a time.

Walkthrough

How to approach it

01Clarify before coding

  • Can values be negative? Yes, the full signed 32-bit range, so the answer may be negative too.
  • Is every other value present exactly three times? Yes, never twice or four times.
  • Is a hash map allowed? Not within the O(1) memory requirement.

02Brute force

Count every value in a hash map and return the one with count 1, or sort and scan groups of three.

Cost: Hash map: O(n) time, O(n) space. Sort: O(n log n) time. Neither meets both bounds.

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.