Finding the Unique Number in a List of Duplicates

 Hey,  💥😋

          can you find the unique number in a list of duplicates? It's an interesting interview question which has many solutions.

Let's have a closer look:

Given: a list or an array having all elements twice except one element, like this:

A = [2, 8, 1, 8, 2]

Expected answer: 1 (i.e. figure out the unique element)

Problem Constraints: 

•  1 <=  length of A <= 3 * 10^4
• -3 * 10^4 <= A[i] <= 3 * 10^4

-----------------------------------------------------------------------------------------------------------------------------

Method 1: Brute force approach

n = length of A     count = 0     for i = 0 to n-1     flag=0     for j = 0 to n-1             if i!=j and A[i] == A[j]       then flag=1 and break         //end inner loop     if flag == 0  //no duplicates found         ans = A[i]             break     print ans

• For this approach:

            Time Complexity: O(n^2)  // two for loops (nested)

            Space Complexity: O(1)  // no extra space used 

-----------------------------------------------------------------------------------------------------------------------------

Method 2: Hashing (to avoid O(n) time for searching)

create a map : m     for i = 0 to n-1:     if (m.find(m[A[i]]) == m.end() ) // if A[i] is not present in map     m[A[i]] = 1     else       m[A[i]] ++  //count increment     // now map has the frequency of all elements     for i = 0 to n-1:         if (m[A[i]] == 1) //occurred only once         then ans = A[i] and break     // end iteration     print ans

• For this approach:

            Time Complexity: O(n)  // for iteration through the list/array

            Space Complexity: O(n)  // extra linear space used 

-----------------------------------------------------------------------------------------------------------------------------

Method 3: Bit Manipulation ⭐

    

    Hint: properties of XOR operation (⊕) : 

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

        [a, b being Boolean variables or bits: 1 or 0]

• Crux: XOR-ing a list of numbers removes duplicates since a ⊕ a = 0, leaving behind the unique number, because a ⊕ 0 = a.

 Hence, solution:

                

ans = 0 for i = 0 to n-1:   ans ^= A[i]   // '^' = bitwise XOR operator print ans

       Time Complexity: O(n)  // for iteration through the list/array

        Space Complexity: O(1)  // no extra space used 

-----------------------------------------------------------------------------------------------------------------------------

   That's it! Explore, practice and move on...💗