How do the XOR solution work this one causes TLE


  • 1
    N
    public int singleNumber(int[] A) {
        for (int i = 0; i < A.length - 2; i++) {
            boolean dupe = false;
    
            for(int j = i + 1; j < A.length; j++) {
                if (A[i] == A[j]) {                    
                    A[j] = A[++i];
                    dupe = true;
    
                    break;
                }
            }
    
            if (!dupe) return A[i];
        }
    
        return A[A.length - 1];
    }

  • 4
    V

    Just need to apply bit operations. XOR will return 0 if two numbers are exactly equal to each other . This XOR operation works because it's like XORing all the numbers by itself. Finally only one number left because A ^ A = 0 and A ^ B ^ A = B. XOR is also a commutative operation.

      class Solution {
            public:
                int singleNumber(int A[], int n) {
                    int result=A[0];
                    for(int i=1;i<n;i++)
                    {
                        result= result^A[i]; 
                   /* Get the xor of all elements */
                    }
                    return result;
                }
            };

  • 0
    S

    Nice solution.Thanks a lot!


  • 0
    V

    I had a similar solution but added a check to see if n was odd else there will be more than one duplicates and is not a correct question.


Log in to reply
 

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