Bit Manipulation — Single Number

↗ LeetCode: Single Number · Easy · pattern chapter →

Asked atMetaAmazonGoogleMicrosoftBloombergAdobe

Every element appears twice except one. Return that one, in O(n) time and O(1) space.

Example 1 — nums=[2,2,1] → 1Example 2 — nums=[4,1,2,1,2] → 4

Constraints — 1 ≤ n ≤ 3·10⁴; all fit in int. Brute HashMap of counts is O(n) time + O(n) space — GC cost dominates at ~10⁶ requests/sec. XOR-fold is O(n) time + O(1) space — 3·10⁴ XOR ops on the hot path, no allocations at all.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — HashSet toggle

Intuition. For each element, add if absent, remove if present. Last surviving element wins.

int singleNumberSet(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) if (!seen.add(x)) seen.remove(x);
    return seen.iterator().next();
}

Complexity — Time O(n); Space O(n). Fails the O(1) space bar.

---

Approach 2 — Sort + pair scan

Intuition. Sort. Walk in steps of 2. The first index where nums[i] != nums[i+1] is the loner.

int singleNumberSort(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; i += 2)
        if (nums[i] != nums[i + 1]) return nums[i];
    return nums[nums.length - 1];
}

Complexity — Time O(n log n); Space O(1) (in-place sort). Doesn't beat the ideal.

---

Approach 3 — XOR fold

Insight. XOR has these algebraic properties: a ^ a = 0 and a ^ 0 = a. Folding XOR over every element cancels every duplicate pair; the survivor is the single number.

int singleNumber(int[] nums) {
    int x = 0;
    for (int v : nums) x ^= v;
    return x;
}

Execution Trace

XOR fold — nums=[4,1,2,1,2]

Step 1 / 50 ^ 4 = 4

Complexity — Time O(n); Space O(1). Optimal.

---

Try it yourself

Complexity summary

Approach	Time	Space
HashSet	O(n)	O(n)
Sort + pair scan	O(n log n)	O(1)
XOR fold	O(n)	O(1)

When to use which

• Cold interview → walk hash set → XOR. The XOR is the "aha" moment interviewers grade for.
• Interviewer probes correctness → state associativity + commutativity of XOR aloud.

✨AI Study CompanionBeta

Related problems (same ladder applies)

• Missing Number — XOR nums with indices; the survivor is the missing index
• Find the Difference — XOR two strings; survivor is the added char
• Single Number II — every element thrice except one; bit-count mod 3
• Single Number III — two loners; XOR gives their xor, then split by any set bit

Was this page helpful?