My O(n) solution with XOR (with Explaination)


  • 0
    C

    So,basically XOR of two numbers whose values are equal is equal to 0.

    For,example 5^5 = 0,4^4 =0.

    We can use this trick in our problem.When we find XOR of every element except the one which appear only once,the value will be 0.

    For example, let the array be ar = [2,2,3,3,4].

    XOR --> 2^2^3^3 = 0 ( XOR of all numbers except one which appear only once)

    Got it.Cool.

    Now the last part.When you XOR a number with 0 , the result is number itself.
    That means if we perform XOR on our entire array,we will get the required answer.

    i.e 2^2^3^3^4 = 0^4 = 4.Hope it helps :)

        class Solution {
        public:
        int singleNumber(vector<int>& nums) {
        
        int i = 0;
        
        int n = nums.size();
        
        int k = nums[0];
        
        for(i = 1;i < n;i++){
            
            k = k ^ nums[i];
            
        }
        
        return k;
        
    }
    

    };


Log in to reply
 

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