Algorithm Day97 - Single Number

Posted on In , Views:

🧩 Problem

LeetCode 136 - Single Number
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.

Example:

1
2
Input: nums = [4,1,2,1,2]
Output: 4

💡 Idea

This problem can be elegantly solved using the XOR (^) operation.
Key properties of XOR:

  • a ^ a = 0
  • a ^ 0 = a
  • XOR is commutative and associative

Thus, when we XOR all numbers together, pairs cancel out, leaving only the unique number.

Example

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

💻 Java Code

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

🧠 Complexity

  • Time: O(n) — iterate once through the array
  • Space: O(1) — only one variable used

🏁 Summary

A perfect example of how bitwise operations simplify logic and improve efficiency.
The XOR trick is commonly used in array problems involving pairs and uniqueness detection.