Skip to main content

7. Single Number

easyAsked at Freshworks

Find the one un-paired ticket ID in a batch where every other ID was acknowledged twice — a classic XOR trick framed as Freshdesk audit reconciliation.

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

Problem

Given a non-empty array of integers where every element appears twice except one, find the single one. Must run in linear time and 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. Brute force with Map

Count occurrences in a hash map and return the key with count 1.

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

Tradeoff:

2. XOR fold

XOR is associative and self-inverse, so x ^ x = 0 and x ^ 0 = x. Fold the whole array under XOR and only the unique element survives.

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

Tradeoff:

Freshworks-specific tips

Freshworks loves when you say the words 'XOR is its own inverse' out loud — it signals you're not just regurgitating a memorized snippet but actually understand the algebra behind the trick.

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

Practice these live with InterviewChamp.AI →