15. Single Number

Q: Why does XOR work here?

XOR has two key properties: n XOR n = 0 (a number cancels itself) and n XOR 0 = n (zero is the identity). Since every duplicate pair cancels to 0, the final XOR of all elements is the unpaired number XOR'd with 0, which is just the number itself.

Q: What if the array contains floating-point numbers?

XOR only works on integers. For floats, you'd need a hash map or sort-based approach. ServiceNow's incident IDs are integers, so this is a non-issue in context.

easyAsked at ServiceNow

Find the one element in an array that appears exactly once when all others appear twice. ServiceNow uses this to test bit-manipulation awareness and O(1)-space thinking — skills that surface when candidates discuss efficient event-deduplication in high-volume incident streams.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

LeetCode Discuss (2025)— Flagged as a ServiceNow SDE-I phone screen puzzle to probe bit-manipulation.
Blind (2026)— Mentioned as a classic ServiceNow warm-up alongside Two Sum.

Problem

Given a non-empty array of integers nums, every element appears exactly twice except for one. Find that single element. You must implement a solution with a 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 exactly twice except for one element which appears exactly once.

Examples

Example 1

Input

nums = [2,2,1]

Output

Explanation: 1 appears once; 2 appears twice.

Example 2

Input

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

Output

Approaches

1. Hash map frequency count

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

Time: O(n)
Space: O(n)

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

Tradeoff: Correct but uses O(n) space — violates the constant-space constraint stated in the problem. ServiceNow interviewers will flag this.

2. XOR bit trick

XOR all numbers together. Pairs cancel to 0 (n XOR n = 0) and 0 XOR x = x, so the result is the single unpaired element. One pass, zero extra memory.

Time: O(n)
Space: O(1)

function singleNumber(nums) {
  let result = 0;
  for (const n of nums) {
    result ^= n;
  }
  return result;
}

Tradeoff: Elegantly satisfies both the O(n) time and O(1) space constraints. The key insight — XOR is commutative and associative, so order doesn't matter — is worth stating aloud to impress ServiceNow interviewers.

ServiceNow-specific tips

ServiceNow interviewers treat this as a signal that you know when bit manipulation is the right tool, not just arithmetic. State the XOR identity properties (a^a=0, a^0=a) before the loop, which shows mathematical reasoning. Bonus: connect the pattern to efficient de-duplication in ServiceNow's event management stream where pairs of duplicate alerts cancel out.

Common mistakes

Initializing result = nums[0] instead of 0 — this works but requires handling the empty-array edge case separately and is less clear.
Using subtraction (2 * sum(set) - sum(array)) — clever but breaks if elements are negative or if integer overflow isn't handled.
Forgetting to mention that XOR is commutative and associative, leaving the interviewer unsure whether you understand WHY it works.

Follow-up questions

An interviewer at ServiceNow may pivot to one of these next:

Single Number II: every element appears three times except one — use a 32-bit counter per bit.
Single Number III: two elements appear once — use XOR to split into two groups.
Find the duplicate number in an array without modifying it (Floyd's cycle detection).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does XOR work here?

XOR has two key properties: n XOR n = 0 (a number cancels itself) and n XOR 0 = n (zero is the identity). Since every duplicate pair cancels to 0, the final XOR of all elements is the unpaired number XOR'd with 0, which is just the number itself.

What if the array contains floating-point numbers?

XOR only works on integers. For floats, you'd need a hash map or sort-based approach. ServiceNow's incident IDs are integers, so this is a non-issue in context.

Practice these live with InterviewChamp.AI

Drill Single Number and other ServiceNow interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →