Skip to main content

19. Single Number

easyAsked at Workday

Given a non-empty array where every element appears twice except for one, find that single one. Workday uses this to gauge whether you can leverage XOR for O(1)-space dedup — useful when audit logs pair every action with its reversal.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

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. Hash map count

Count each value, return the one with count == 1.

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

Tradeoff: O(n) extra space. Violates the constant-space constraint.

2. XOR fold

XOR is associative + commutative + self-inverse: a^a=0, a^0=a. Folding the whole array leaves the loner.

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

Tradeoff: Two-line solution. The insight is that XOR of identical numbers is 0, so all the duplicates cancel.

Workday-specific tips

Workday grades for citing the algebraic properties of XOR (commutative, associative, self-inverse) before coding. Bonus signal: mention that this generalizes to 'every element appears three times except one' via a 32-bit per-position counter (LC 137).

Common mistakes

  • Using a hash map — violates O(1) space.
  • Trying sort + linear scan — O(n log n) and may mutate input.
  • Not knowing why XOR works — interviewer will ask 'why?'.

Follow-up questions

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

  • Single Number II (LC 137) — appears three times except one.
  • Single Number III (LC 260) — two unique numbers.
  • Missing Number (LC 268) — XOR with index trick.

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 is commutative (a^b = b^a) and self-inverse (a^a = 0). So you can reorder the array so duplicates are adjacent — they cancel pairwise, leaving the loner XORed with 0, which is itself.

What if there were three of each except one?

XOR alone doesn't work. Use a 32-bit counter array or two-bit-state automaton — that's LC 137.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →