Single Number - C++ Solution


  • 0
    M

    Approach 1: Using HashTable [Accepted]

    Concept:

    Store all seen elements in Hash Table with number of times the element is seen as the value corresponding to each key. At the end when all the elements are stored in hash table iterate over hash table and find value where key value is 1.

    Algorithm:

    1. Initialize a empty hash table.
    2. Iterate over nums. If current element is present in hash table then increment value corresponding to current element by 1. Else make entry in hash table with current element as key and it's value as 1.
    3. Once all the elements of nums are seen then iterate over hash table to find which element has single occurrence.

    Code:

    int singleNumber(vector<int>& nums){
    
        std::map<int,int> table;
    
        for (auto x: nums){
            if(table.find(x) == table.end()){
                table[x] = 1;
            }   
            else{
                ++table[x];
            }   
        
        }   
    
        for(auto x : table){
            if(x.second == 1){ 
                return x.first;
            }   
        }   
        return -1; 
    }
    

    Complexity:

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

    Approach 2: Using XOR [Accepted]

    Concept:

    Bitwise XOR exhibits below properties:

    • a ^ 0 = a
    • a ^ a = a

    As all the numbers except one number are present twice, so XOR'ing all the elements of nums would give us the single number in nums.

    Algorithm:

    1. Start with result = 0.
    2. Iterate over each element of nums and perform XOR of result with current element.
    3. Return result.

    Code:

    #include<algorithm>
    #include<numeric>
    
    int singleNumber(vector<int>& nums){
        return std::accumulate(nums.begin(),nums.end(),0,std::bit_xor<int>() );
    }
    

    Complexity:

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.