Problem Explanation

We are given a non empty array where all elements are repeated twice except one. We need to find that number.

Examples :

nums = [1,3,1,2,3,2]
Output: 2

nums = [5]
Output: 5

Different approaches to solve the problem

Brute Force - Two loops

Idea : For each element, count how many times that element occurred. If the count of any element is 1 return that element. As we need two loops, time complexity for this approach is O(N*N). We don't need any additional space except counter variable. So space complexity is O(1)

if len(nums) == 1 :
    return nums[0]

# run two loops and for each ele find the count.

for i in range(len(nums)) :
    count = 0
    for j in range(len(nums)) :
        if nums[i] == nums[j] :
            count += 1

    # check the count

    if count == 1 :
        return nums[i]

# Time Complexity: O(N * N) 
# Space complexity: O(1)

Hashing method

Idea : Instead of traversing again for each element, we store the counts of each element. In the end we simply traverse again in the counter and return the element whose count is 1.

if len(nums) == 1 :
    return nums[0]

counter = {}  # dictionary to keep track of elements

for ele in nums :
    if ele in counter :
        counter[ele] += 1  # increase the count, if ele already visited
    else :
        counter[ele] = 1   # when we visit element for the first time

# traverse the dictionary and find the ele with count = 1

for ele, count in counter.items()  :
    if count == 1 :
        return ele


# Time Complexity: O(N) 
# space complexity: O(N)  (we will be storing N/2 ele in dictionary)

Can we do better than this? Can we somehow eliminate extra space? Yes. We can do using bit manipulation techniques...

XOR Method - Best approach

Quick recap of XOR properties :

• a ^ a = 0
• a ^ b = 1 if a != b else 0
• a ^ 0 = a
• xor is associative and commutative.

How can we best use of the above properties. if we think about it, xor of all elements will directly give single repeating number. It is because of xor of two duplicate numbers is 0 and all duplicates will be cancelled.

res = nums[0]

for ele in nums[1 :] :
    res = res ^ ele

return res

# Time Complexity: O(N) 
# Space complexity: O(1)

Conclusion

If you have understood the solution, practice this question in leetcode .

Any feedback or suggestions are always welcome.