find the NON DUPLICATE number from the given array-CodePudding

Given an array of n integers, every number appears twice except for one. we have to find the one with a single occurrence.

This is the solution to the question, written in python, but I don't understand how it works.

How does the code work?

def FindtheNumber(arr):
   for a in arr:
       counter = 0
       for b in arr:
          if a == b: 
            counter  = 1
       if counter == 1:
          return a
          

arr=[1,2,2,1,3]
print(FindtheNumber(arr))

CodePudding user response：

So basically your code Iterate through every element in the arr and check if any of the element does not appear twice, in that case return the element.

Time complexity O(n^2) Space Complexity O(1)

You can Improve your time complexity to O(n).

Intuition.. Using bit manipulation.

Xor of any two num gives the difference of bit as 1 and same bit as 0. Thus, using this we get 1 ^ 1 == 0 because the same numbers have same bits. So, we will always get the single element because all the same ones will evaluate to 0 and 0^single_number = single_number. Note Xor follows commutative as well as associative property..

Code:- Time Complexity O(n) Space Complexity O(1)

def FindtheNumber(arr):
    xor=0
    for number in arr:
        xor=xor^number
    return xor
          
arr=[1,2,2,1,3]
print(FindtheNumber(arr))

CodePudding user response：

It actually counts how many times element "a" is in the array. Since we know that "a" is in the array, the counter keeps track of the amount of time "a" is in the array. If this is 1, that means that we've find our number wich is exactly 1 time in the array.

Hope this makes it a little more clear:)

CodePudding user response：

Here's how the code works. Essentially, it considers each element of the array, and counts how many times it appears in the array by comparing with every element of the array (that is, everytime a == b is true), even with itself.

If count == 1 is true, that means that the element as appeared only once, since the counter has increased when the element encountered itself.

The code is very inefficient though (O(n^2) time complexity), and could be more (time) efficient using an hashmap to keep a counter for each value, and check the hashmap afterwards to find the counter that is equal to 1. In this way, it would be very slight more complex in space, but time complexity will be O(2n), which is much better.

Hope this helps!