Skip to main content

8. Single Number

easyAsked at Wise

Find the one unpaired transaction in a stream where every other entry has a matching counter-entry — a tiny model of ledger reconciliation at Wise.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given a non-empty array of integers where every element appears twice except for one, find that single one. Solve in linear time and constant extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • Every element appears twice except one
  • O(1) extra space required

Examples

Example 1

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

Example 2

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

Approaches

1. Hash map count

Tally each integer, 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:

2. XOR fold

XOR is its own inverse, so paired entries cancel and the lone entry survives. Constant space and one pass.

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

Tradeoff:

Wise-specific tips

Wise interviewers love this XOR insight because ledger reconciliation is exactly the production analogue — paired debit/credit entries cancel and the unmatched leg is the bug.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Wise coding interview questions

See all Wise problems →

Companies that also ask Single Number