[Bit Manipulation] Single Number

[sudosf]

Problem

Given a non-empty array where every element appears twice except for one, find that single element. Must run in O(n) time and O(1) space.

References

• LeetCode: https://leetcode.com/problems/single-number/
• GFG: https://www.geeksforgeeks.org/problems/element-appearing-once2552/1
• Sheet: https://www.risingbrain.org/sheet#bit-manipulation (Basic Bit Operations [Two Pointer] 3Sum #6)
• Parent: Pattern: Bit Manipulation #150

Difficulty

🟢 Easy

Companies

Amazon, Google, Microsoft

Notes

Language: Java
XOR all elements. Pairs cancel out (a ^ a = 0). Result is the single element.