Given a non-empty array of integers, every element appears twice except for one. Find that single element.

In Simple Words ! The problem "Single Number" asks us to find the element that appears only once in an array where every other element appears twice.

Let's break down the problem and explore the three approaches

Approach 1: Brute Force

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int num = 0;
        for (int i = 0; i < nums.size(); i++) {
            bool found = false;
            for (int j = 0; j < nums.size(); j++) {
                if (i != j && nums[i] == nums[j]) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                num = nums[i];
                break;
            }
        }
        return num;
    }
};

1. Iterate through each element in the array.
2. For each element, check if it appears again in the array (excluding itself).
3. If no duplicate is found, mark the element as the single number.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> hashTable;
        for (int num : nums) {
            hashTable[num]++;
        }
        for (auto& pair : hashTable) {
            if (pair.second == 1) {
                return pair.first;
            }
        }
        return -1; // Should not reach here
    }
};

Explanation:

1. Create a hash table to store the frequency of each number.
2. Iterate through the array and increment the frequency of each number.
3. Iterate through the hash table and find the number with frequency 1.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> hashTable;
        for (int num : nums) {
            hashTable[num]++;
        }
        for (auto& pair : hashTable) {
            if (pair.second == 1) {
                return pair.first;
            }
        }
        return -1; // Should not reach here
    }
};

1. Initialize ans to 0.
2. Iterate through the array and XOR each number with ans.
3. The XOR operation has the following properties:
• a ^ a = 0 (self-inverse)
• a ^ 0 = a (identity)
• a ^ b = b ^ a (commutative)
• (a ^ b) ^ c = a ^ (b ^ c) (associative)