Skip to main content

12. Single Number

easyAsked at LINE

Find the element that appears exactly once when every other element appears twice — LINE uses this to test whether you reach for XOR before a hash map, the same shape as deduping read-receipt acks.

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

Problem

Given a non-empty array of integers nums where every element appears twice except for one, find that single one. Your solution should run in linear time and constant extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • Each element appears twice except for one that appears once.

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

Count occurrences and return the key with count 1.

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

Tradeoff:

2. XOR accumulator

XOR is associative, commutative, and x ^ x === 0. XOR every element together and the duplicates cancel, leaving the unique value.

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

Tradeoff:

LINE-specific tips

At LINE, frame this as the same cancellation trick they use when reconciling duplicate read-receipt acks delivered by parallel push routes — presence-pipeline framing wins.

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 LINE interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →