Problem Statement : We are given an array of n integers in which every number appears twice except two numbers which appear only once. We need to find those two numbers which appear in O(n) time complexity and O(1) space complexity.
Hints and ideas: -
· Consider a simpler problem in which we have to find only 1 non repeating element in the array of elements where every other element appears twice. This can be solved in O(n) time and O(n) space by using a map in C++ or a dictionary in python to store the number of occurrences of each number (frequency table) and we just output the number which appears once.
· However, to obtain O(1) space we should consider a way to efficiently not consider those numbers which appear twice. Is there any operation or method you know of which will help eliminate those elements which appear twice and which leaves you with the unique number in O(1) space?
· Think bitwise (what does the xor operation do?)
· Let us review some basic xor operations – a^0 = a for any integer a, b^a = a^b for integers a,b and most importantly a^a = 0. Using this we could just do the xor of all the numbers in the array leaving us with the answer since all the numbers which appear twice will effectively cancel each other while doing the xor.
· Now that we can tackle the easier question (whose code should not be difficult since we just do the xor of all the array elements) let us think about the harder problem.
In this approach we just store the frequency of each number and output those two which appear twice. We use the c++ unordered map since it is faster than the normal map.
Time complexity : O(n)
Space complexity : O(n)
· We follow the hints and take the bitwise xor of all the elements in the array. However, this only will give us “res” = a^b where “a” and “b” are the two unique numbers of the array which we need to output.
· Now let us consider a set bit in res – A bit at position ‘i’ will be set only if the two numbers a and b are at the same position ‘i’ . This follows from the definition of xor. Similarly, a bit at position ‘j’ will not be set if a and b both have the same bit at position ‘j’ .
· Note that there will be at least 1 set bit in res otherwise we would have a = b and each number in the array occurs twice which is not possible.
· Thus, we find the first set bit (actually any set bit will do the job) from the right and we can separate the original array into two parts based on whether an element has that bit set or not. This will result in “a” and “b” being in different parts of the array and all equal numbers will also be in the same part of the array. As a result, we just take xor of each part of the array to obtain “a” and “b”.
· Let me illustrate with an example – let A = [1,1,2,2,3,3,4,5,5,6,7,7]. Note that A need not be sorted but we can assume that it is sorted without loss of generality since we do not care about the order of the elements in A.
· Taking the bitwise xor of all numbers we obtain “res” = 6^4 = 2 (110 ^ 100 = 010)
· Now consider the set bit (2nd bit from the right). If we split A into two sections based on whether an element has the 2nd bit set or not, we obtain part1 = [3,3,6,7,7] and part2 = [1,1,2,2,4,5,5]. Note that the actual elements of part1 and part2 do not matter as our only objective is that the integers “a” and “b” are in different parts and that all the numbers in part1 and part2 except “a” and “b” appear twice. As a result, we just take xor of all numbers in part1 and part2 and obtain a = 6 and b = 4 as our answer.
Time complexity : O(n)
Space complexity : O(1)
It is highly recommended to solve one practice problems as it will help you understand this concept more clearly
This article is contributed by Adhish Kancharla
So that’s it for this article we will be coming up with our next article on further topics of Algorithms very soon till then keep learning, keep coding, keep reading and keep improving !!
Happy Coding
By Programmers Army 😊