Skip to main content

9. Single Number

easyAsked at Klarna

Find the one element that appears exactly once in an array where every other element appears twice.

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. Your solution must run in linear time and use constant extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • Exactly one element appears once; all others appear twice

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

Count occurrences in a map, then scan for count==1.

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

Tradeoff:

2. XOR fold

Pairs cancel under XOR, so XOR-folding the whole array leaves only the unique value. Constant space.

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

Tradeoff:

Klarna-specific tips

Klarna risk-feature engineers grade this on whether you reach for the XOR trick fast; they reuse it for parity checks across replicated installment-ledger shards.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Klarna coding interview questions

See all Klarna problems →

Companies that also ask Single Number