Skip to main content

7. Single Number

easyAsked at Swiggy

In an array where every element appears twice except one, find the unique value.

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

Problem

Given a non-empty integer array where every element appears exactly twice except one, return the unique element. Aim for linear time and constant extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • All elements appear twice except one
  • -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. Hash map count

Count occurrences, return the one with count 1.

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

Tradeoff:

2. XOR fold

XOR is commutative and self-inverse, so XOR-ing every element cancels out duplicates and leaves the unique value. O(1) space.

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

Tradeoff:

Swiggy-specific tips

Swiggy rewards the XOR insight because it shows comfort with bitwise reasoning, useful for the order-ID deduplication problems they layer in later.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Swiggy coding interview questions

See all Swiggy problems →

Companies that also ask Single Number