8. Single Number

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

Example 1:
Input: [2,2,1]
Output: 1

Example 2:
Input: [4,1,2,1,2]
Output: 4

Using Hashmap

Caching

Caching or Indexing is a technique used to store counts of values which lie in a small range.

class Solution
{
public:
    int singleNumber(vector<int> &nums)
    {

        unordered_map<int, int> m;
        int val;
        for (int i = 0; i < nums.size(); i++)
        {
            if (m.find(nums[i]) == m.end())
            {
                m.insert({nums[i], 1});
            }
            else
            {
                m[nums[i]]++;
            }
        }

        for (auto i = m.begin(); i != m.end(); i++)
        {
            if (i->second == 1)
            {
                val = i->first;
                break;
            }
        }

        return val;
    }
};

Time Complexity :O(n) , Space Complexity:O(n)

Using XOR

Concept

• If we take XOR of zero and some bit, it will return that bit

  • a xor 0 = a⊕0 = a

• If we take XOR of two same bits, it will return 0

  • a xor a = a⊕a= 0

  a⊕b⊕a = (a⊕a) ⊕ b = 0 ⊕ b = b

class Solution
{
public:
    int singleNumber(vector<int> &nums)
    {

        int val = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            val = val ^ nums[i];
        }

        return val;
    }
};

Time Complexity :O(n) , Space Complexity:O(1)