136. Single Number - Detailed Explanation

Java Code (Brute Force):

Approach 2: Optimal Solution Using XOR

Explanation:

• Initialize a variable result with 0.

• Iterate through each number in the array and perform the XOR operation with result:

  • result ^= num

• The XOR operation cancels out duplicate numbers (because a ^ a = 0), leaving the unique number.

• Time Complexity: O(n)

• Space Complexity: O(1)

Python Code (Optimal XOR):

Complexity Analysis:

• Brute Force (Hash Table):
  • Time Complexity: O(n)
  • Space Complexity: O(n)
• Optimal (XOR):
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Edge Cases:

1. Single Element Array:
   • Example: [x] should return x.
2. Array with Negative Numbers:
   • The XOR approach works correctly with negative numbers as well.
3. Large Arrays:
   • Ensure the algorithm can handle arrays of maximum allowed size efficiently.

Common Mistakes:

1. Using Extra Space Unnecessarily:
   • While the hash table approach is valid, it does not meet the optimal space requirement.
2. Incorrect XOR Initialization:
   • Forgetting to initialize the result to 0 or misusing XOR operations can lead to errors.
3. Overlooking Edge Cases:
   • Ensure that the solution handles cases such as a single-element array or arrays with negative numbers.

Alternative Variations:

1. Single Number II (LeetCode 137):
   • Every element appears three times except for one. A different bit manipulation approach is needed.
2. Single Number III (LeetCode 260):
   • Two numbers appear once while all others appear twice. The problem requires finding the two unique numbers.

Related Problems for Further Practice:

1. Single Number II (LeetCode 137)
2. Single Number III (LeetCode 260)
3. Missing Number (LeetCode 268)
4. Find the Duplicate Number (LeetCode 287)