Introduction

The Single Number problem involves finding the element that appears exactly once in an array.

Given an integer array arr[]:

  • every element appears twice
  • except one element

The task is to find that unique element.

This problem introduces an important bit manipulation concept:

 XOR Operation

This problem helps in understanding:

  • hashing techniques
  • bit manipulation
  • XOR properties
  • optimized traversal

Example

Input:arr[] = [2,2,1]
Output:
1
Explanation:
2 appears twice
1 appears only once

Input:
arr[] = [4,1,2,1,2]
Output:
4
Explanation:
1 and 2 appear twice
4 appears once

Constraints

 1 <= n <= 3 * 10^4 -3 * 10^4 <= arr[i] <= 3 * 10^4 Every element appears twice except one

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Traverse every element
  2. Count its frequency
  3. Return the element having frequency 1

This approach is easy to understand but repeated counting increases time complexity.

Steps

  1. Traverse array using index i.
  2. Count frequency of arr[i].
  3. If frequency becomes 1:
    • return element
  4. Continue traversal otherwise.

Dry Run

Input:arr = [4,1,2,1,2]

Traverse 4:
Frequency = 1
Single number found
Return 4

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)Explanation:
Nested traversal is used for counting frequencies.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Approach 2 : Better Solution (Hashing)

Explanation

Instead of repeatedly counting frequencies, we can use hashing.

The idea is:

  1. Store frequencies in hashmap
  2. Traverse hashmap
  3. Return element having frequency 1

This reduces time complexity significantly.

Steps

  1. Create hashmap.
  2. Store frequencies.
  3. Traverse hashmap.
  4. Return element with frequency 1.

Dry Run

Input:arr = [4,1,2,1,2]

Store frequencies:
4 → 1
1 → 2
2 → 2

Traverse hashmap:
4 has frequency 1
Return 4

Better Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Array is traversed once for frequency counting.

Space Complexity: O(n)
Explanation:
Extra hashmap is used.

Approach 3 : Optimized Solution (XOR Technique)

Explanation

The optimized solution uses XOR properties:

a ^ a = 0a ^ 0 = a

This means:

  • duplicate elements cancel each other
  • only single number remains

This provides:

  • O(n) time
  • O(1) space

Steps

  1. Initialize answer = 0.
  2. Traverse array.
  3. XOR every element with answer.
  4. Final answer becomes single number.

Dry Run

Input:arr = [4,1,2,1,2]

Initially:
answer = 0

XOR 4:
0 ^ 4 = 4
answer = 4

XOR 1:
4 ^ 1 = 5
answer = 5

XOR 2:
5 ^ 2 = 7
answer = 7

XOR 1:
7 ^ 1 = 6
answer = 6

XOR 2:
6 ^ 2 = 4

Final Result:
4

Optimized Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Each element is processed once.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Edge Cases

  1. Array contains one element
  2. Single number present at beginning
  3. Single number present at end
  4. Negative numbers present
  5. Large array size

Why This Problem is Important

This problem helps in understanding:

  1. XOR operations
  2. Bit manipulation
  3. Hashing techniques
  4. Frequency problems
  5. Optimized traversal

It is one of the most important beginner-level bit manipulation interview problems.

Real-World Applications

XOR concepts are used in:

  1. Cryptography
  2. Error detection systems
  3. Data compression
  4. Memory optimization
  5. Networking systems

Common Mistakes

  1. Incorrect XOR understanding
  2. Forgetting duplicate cancellation
  3. Wrong hashmap updates
  4. Returning incorrect value

Interview Tips

Interviewers often expect:

  1. XOR optimization
  2. Bit manipulation explanation
  3. O(1) space solution

Always explain why duplicate numbers cancel each other using XOR.

Related Questions

  1. Missing Number
  2. Find Duplicate
  3. Two Single Numbers
  4. XOR Queries
  5. Majority Element

Final Takeaway

The Single Number problem is a fundamental bit manipulation problem that teaches XOR optimization and duplicate cancellation techniques. Understanding this problem builds a strong foundation for advanced hashing and bitwise interview problems.