Skip to main content

9. Single Number

easyAsked at N26

Given a non-empty array where every element appears twice except for one, find the single one. N26 uses this to test bitwise fluency before deeper ledger-reconciliation problems where one unmatched debit needs to be isolated.

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

Problem

Given a non-empty integer array nums where every element appears twice except for one, return that single element. Your algorithm should have linear runtime and use constant extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • Every element except one appears exactly twice
  • -3 * 10^4 <= nums[i] <= 3 * 10^4

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

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 x of nums) m.set(x, (m.get(x)||0)+1);
for (const [k,v] of m) if (v===1) return k;

Tradeoff:

2. XOR accumulation

XOR is associative and a^a=0, so XOR-ing every element cancels duplicates and leaves the unique value.

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

Tradeoff:

N26-specific tips

N26 likes you to call out that the same XOR-cancel trick spots the single unmatched leg when batching SEPA debit-credit pairs for end-of-day reconciliation.

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

Practice these live with InterviewChamp.AI →