Skip to main content

18. Single Number

easyAsked at Zoom

Find the element appearing once when all others appear twice.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given a non-empty array of integers where every element appears twice except for one, find the one that appears once. Solve in linear time and constant space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • Each except one appears exactly 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

Count occurrences then find the count-1 key.

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 fold

x ^ x = 0 and x ^ 0 = x, so XOR-ing the array leaves the unique value.

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

Tradeoff:

Zoom-specific tips

Zoom asks XOR problems to confirm bit-level fluency — useful since their audio codec sync uses XOR checksums for packet integrity.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Zoom coding interview questions

See all Zoom problems →

Companies that also ask Single Number