Skip to main content

13. Single Number

easyAsked at GitLab

Find the element that appears exactly once in an array where every other element appears twice.

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

Problem

Given a non-empty integer array where every element appears twice except for one, find the unique element. Use only constant extra space.

Constraints

  • 1 <= nums.length <= 3*10^4
  • Exactly one element appears once; all others appear 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 counts

Count occurrences, return the key with count 1. Violates the O(1) space rule.

Time
O(n)
Space
O(n)
const c={};
for (const x of nums) c[x]=(c[x]||0)+1;
for (const k in c) if (c[k]===1) return +k;

Tradeoff:

2. XOR fold

XOR is associative and self-inverse, so XORing every element cancels the pairs and leaves the singleton.

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

Tradeoff:

GitLab-specific tips

GitLab leans on the XOR insight to gauge whether you can apply algebraic properties to dedup events streaming from many runners without a side hash table.

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

Practice these live with InterviewChamp.AI →