Skip to main content

14. Single Number

easyAsked at Palantir

Given a non-empty array of integers where every element appears twice except for one, find that single one. Palantir asks this to see if you reach for XOR — a constant-space trick they value when streaming dedup logic runs on row-level entity resolution in Foundry.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2025-11)— Palantir FDE phone-screen — interviewer specifically asked for O(1) space.
  • Reddit r/cscareerquestions (2026-Q1)— Tagged as Palantir 'XOR trick' question.

Problem

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with linear runtime complexity and use only constant extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Each element in the array appears twice except for one element which appears only once.

Examples

Example 1

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

Example 2

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

Example 3

Input
nums = [1]
Output
1

Approaches

1. Hash map frequency count

Count occurrences of each number; return the one with count 1.

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

Tradeoff: Linear but uses O(n) space — fails the explicit O(1)-space constraint Palantir asks for.

2. XOR accumulator

XOR all numbers together. Pairs cancel (x ^ x = 0); the unique number remains.

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

Tradeoff: Linear time, constant space, no hashing. The 3-line solution is exactly the signal Palantir wants.

Palantir-specific tips

Palantir interviewers ask this specifically because the optimal solution is non-obvious — they want to see if you know the XOR cancellation property. Drop the two properties out loud: (1) XOR is associative and commutative, so order doesn't matter; (2) x ^ x = 0 and x ^ 0 = x. Bonus signal: mention that this pattern generalizes to finding the single element when others appear three times (LC 137) using bit-counting mod 3 — even if you don't code it.

Common mistakes

  • Using Set and toggling add/delete — works but wastes O(n) memory the problem forbids.
  • Sorting and scanning pairs — O(n log n), violates the linear-time requirement.
  • Initializing acc to nums[0] and starting from i=1 — works but breaks if the loop body checks i bounds; safer to start from 0.

Follow-up questions

An interviewer at Palantir may pivot to one of these next:

  • Single Number II (LC 137) — every element appears three times except one.
  • Single Number III (LC 260) — two unique elements.
  • Find missing number in [0..n] (LC 268) — XOR variant.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does XOR work for this?

XOR is commutative and associative, so we can reorder the operations. Each pair XORs to 0, and 0 XOR'd with the unique value gives back the unique value. The order of the elements in the array does not matter.

Does this work for negative integers?

Yes — XOR operates on the two's-complement bit pattern, so signed and unsigned both work. JavaScript's ^ is 32-bit, which is fine given the problem constraints.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →