Skip to main content

15. Single Number

easyAsked at Electronic Arts

Find the element that appears only once in an array where every other element appears twice, testing bit manipulation knowledge used in EA's low-level engine code.

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

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 <= 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

Approaches

1. Hash map count

Count occurrences with a map and return the key with count 1.

Time
O(n)
Space
O(n)
function singleNumber(nums) {
  const map = {};
  for (const n of nums) map[n] = (map[n] || 0) + 1;
  return +Object.keys(map).find(k => map[k] === 1);
}

Tradeoff:

2. XOR bit trick

XOR of a number with itself is 0, and XOR with 0 is the number itself. XOR-ing all elements cancels pairs and leaves the single element. This O(1) space solution is the expected answer in EA engine interviews.

Time
O(n)
Space
O(1)
function singleNumber(nums) {
  return nums.reduce((acc, n) => acc ^ n, 0);
}

Tradeoff:

Electronic Arts-specific tips

EA interviews cover game development data structures, pathfinding (A*, BFS on grids), spatial algorithms, and simulation problems. Grid/matrix manipulation and BFS on 2D arrays are very common.

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

Practice these live with InterviewChamp.AI →