Skip to main content

16. Single Number

easyAsked at PayPal

Find the one element in an array that appears exactly once while all others appear exactly twice. PayPal uses this to probe XOR bit-manipulation knowledge and constant-space thinking — skills tied to low-level transaction-ID deduplication logic.

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

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • LeetCode Discuss (2025)— PayPal OA included Single Number as a warm-up before harder problems
  • Reddit r/cscareerquestions (2025)— Thread on PayPal phone screens mentioned bit manipulation questions

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 <= 30000
  • -30000 <= nums[i] <= 30000
  • 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

Explanation: 4 appears once; 1 and 2 each appear twice

Approaches

1. Hash map frequency count

Count occurrences of every element in a map and return the one with count 1.

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

Tradeoff: O(n) space violates the constant-space constraint — good to mention, then optimize.

2. XOR bit manipulation

XOR of a number with itself is 0; XOR with 0 is the number itself. XOR-ing all array elements cancels every duplicate pair, leaving only the single element. O(n) time, O(1) space.

Time
O(n)
Space
O(1)
function singleNumber(nums) {
  let result = 0;
  for (const n of nums) {
    result ^= n; // duplicate pairs cancel out: n ^ n = 0
  }
  return result; // only the unique element remains
}

Tradeoff: Elegant one-liner that satisfies both constraints. At PayPal, mention that XOR is used in checksum and error-detection layers of payment protocols — it shows financial-system domain awareness.

PayPal-specific tips

PayPal interviews focus on payment processing, fraud detection logic, financial reconciliation algorithms, and distributed transaction design. Hash maps, sliding windows, and two-pointer techniques appear frequently.

Common mistakes

  • Starting result at 1 instead of 0 — XOR identity element is 0, not 1
  • Using sorting (O(n log n)) when O(n) is required
  • Forgetting that XOR is commutative and associative — order of elements doesn't matter

Follow-up questions

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

  • What if two elements appear once and all others twice? (LC 260 — XOR + bit partitioning)
  • What if one element appears once and all others three times? (LC 137 — 32-bit counting)
  • Generalize: find the element that appears k times when all others appear m times

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 here?

XOR is its own inverse: x ^ x = 0 for any x, and x ^ 0 = x. XOR-ing the entire array reduces all pairs to 0, leaving the unpaired element untouched.

Does the order of elements matter?

No — XOR is commutative and associative, so the result is the same regardless of element order.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →