Skip to main content

10. Single Number

easyAsked at Riot Games

Find the only element that appears once in an array where every other element appears twice — a bitwise trick Riot favors for low-overhead anti-cheat heuristics.

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

Problem

Given a non-empty array of integers where every element appears twice except for one, find that single element. Solve it with linear runtime complexity and without extra memory.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • Every element except one appears twice

Examples

Example 1

Input
nums=[2,2,1]
Output
1

Example 2

Input
nums=[4,1,2,1,2]
Output
4

Approaches

1. Hash map count

Tally occurrences and return the key with count 1.

Time
O(n)
Space
O(n)
const c = new Map();
for (const n of nums) c.set(n,(c.get(n)||0)+1);
for (const [k,v] of c) if (v===1) return k;

Tradeoff:

2. XOR fold

XOR all elements; pairs cancel out and the lone element remains. Same trick Riot uses to compress per-tick replication deltas into a single hashable signature.

Time
O(n)
Space
O(1)
function singleNumber(nums) {
  let acc = 0;
  for (const n of nums) acc ^= n;
  return acc;
}

Tradeoff:

Riot Games-specific tips

Riot interviewers grade bonus points when you derive XOR's pair-cancellation property aloud — they use the same constant-space fingerprint trick when checksumming server tick states against client packets.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Single Number and other Riot Games interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →