Skip to main content

19. Single Number

easyAsked at Datadog

Every element appears twice except one. Find the singleton in O(n) time and O(1) space. Datadog asks this to test whether you know the XOR trick — a streaming-friendly aggregate that uses constant memory regardless of cardinality.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog backend question — graded on the XOR insight.
  • Blind (2025-12)— Recurring Datadog problem; lead-in to bit-manipulation rounds.

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 a 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. Hashmap count

Count occurrences; return the key with count 1.

Time
O(n)
Space
O(n)
function singleNumber(nums) {
  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: Violates the O(1) space constraint. Datadog will fail this for missing the XOR insight.

2. XOR aggregation (optimal)

XOR is associative and commutative. a XOR a = 0, x XOR 0 = x. XORing all values cancels duplicates, leaving the singleton.

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

Tradeoff: Single-variable accumulator, O(1) state. Streaming-friendly: works on a one-pass infinite stream. Exactly the pattern Datadog uses for count-tracking aggregates.

Datadog-specific tips

Datadog will follow up with: 'What if some elements appear three times?' Show that XOR alone breaks because a XOR a XOR a != 0. The general pattern uses bit-counts mod k (here k=3) — articulate this before coding.

Common mistakes

  • Using a Set and toggling (add if absent, remove if present) — works but uses O(n) memory.
  • Forgetting that XOR is commutative — the order doesn't matter, which makes it streaming-safe.
  • Trying to subtract or add instead of XOR — fails on negatives and overflows.

Follow-up questions

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

  • Single Number II (LC 137) — every element appears 3 times except one.
  • Single Number III (LC 260) — two singletons among pairs.
  • Datadog-style: streaming XOR over a metric ID space to detect dropouts.

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?

XOR cancels equal pairs (a XOR a = 0) and is order-independent. So XORing all elements leaves only the unpaired one.

Does it work on negative numbers?

Yes. XOR operates on the bit representation, including the sign bit. The math holds regardless of sign.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →