Hello everyone ...
Here we are going to solve a Competitive Programming problem related to Bit Manipulation.
Problem Statement
Given an array A containing 2*N+2 positive numbers, out of which 2*N numbers exist in pairs whereas the other 2 numbers occur exactly once and are distinct. Find the two non-repeating numbers.
Examples
Input:
N = 2
arr[] = {1, 2, 3, 2, 1, 4}
Output:
3 4
Explanation:
3 and 4 occur exactly once.Input:
N = 1
arr[] = {2, 1, 3, 2}
Output:
1 3
Explanation:
1 3 occur exactly once.Constraints
1 <= Length of array <= 106
1 <= Elements in array <= 5 * 106
Expectations
Expected Time Complexity: O(N)
Expected Space Complexity: O(1)Problem Link: https://practice.geeksforgeeks.org/problems/finding-the-numbers0215/1
Solution
The first idea that might come to your mind is to use Sorting and comparing adjacent elements in the sorted array to find the non-repeating elements. This solution's time complexity is O(N*logN). But we are expected to solve this with the time complexity of O(N).
Another idea that might come to your mind is to use Hashing to keep track of the frequency of occurrence of each number in an array and then get numbers with the frequency 1, i.e, non-repeating elements. This solution's space complexity is O(N). But we are expected to solve this with the space complexity of O(1).
We can leverage the bitwise XOR operation's logic to solve this problem with the time complexity of O(N) and space complexity of O(1).
Approach
Before going to the actual approach let's understand a bit about bitwise XOR operation.
bit1 | bit2 | bit1 ^ bit2 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0
Decimal | Binary
A = 10 | 1010
B = 7 | 0111
A^B = 13 | 1101Two points to keep in mind before we go forward,
- The result of the XOR operation between two bits will be 1 only if both the bits are different, else 0.
- The result of the XOR operation between the two same numbers will always be 0.
Now let's solve this problem
- Let x and y be the two distinct non-repeating numbers that we need to find in array A.
- Let's calculate the XOR of all the numbers in array A. This will be equal to XOR between x and y because except x and y all other numbers appeared twice in array A and we know that the XOR of two same numbers will always be 0.
- Let's store the above calculated XOR in a variable named x_xor_y
- Since x and y are distinct, there will be at least one set bit in x_xor_y. let's consider the Right Most Set Bit of x_xor_y and let its position be k. From this, we can infer that the kth bit is set in one of x and y, and it is not set in other.
- Now divide the elements of the array into two sets – one set of elements with the kth bit set and another set with the kth bit not set. By doing so, we will get x in one set and y in another set.
- Now if we do XOR of all the elements in the first set, we will get the first non-repeating element, and by doing the same in other sets we will get the second non-repeating element. Because in each set there will be exactly one non-repeating element and the rest appears twice.
Example
A[] = {2, 4, 3, 7, 9, 2, 3, 4}
Decimal | Binary
2 | 0010
3 | 0011
4 | 0100
7 | 0111
9 | 1001
x_xor_y = 2 ^ 4 ^ 3 ^ 7 ^ 9 ^ 2 ^ 3 ^ 4
= 7 ^ 9
= 14 ( 1110 )
^
k (right most set bit position)
set1 = {2, 3, 7, 2, 3} // having kth bit set
set2 = {4, 9, 4} // having kth bit unset
set1_xor = 2 ^ 3 ^ 7 ^ 2 ^ 3
= 7 // non-repeating number
set2_xor = 4 ^ 9 ^ 4
= 9 // non-repeating numberTo check if the number is having a kth bit set, we can do a bitwise AND operation between this number and a number having only a kth bit set. If the result of the above operation is 0 then the kth bit is not set, else the kth bit is set.
1010 1010 & 0010 & 0100 ------ ------ 0010 0000 ------ ------
Now we need a way to turn off all the bits of a number x_xor_y except the rightmost set bit. Because we need that for dividing the array into two sets as we discussed above.
To turn off all the bits of a number(n) except the rightmost set bit, we can use n & ~(n-1).
To understand how the above expression works, we need to understand that Subtracting 1 from a decimal number flips all the bits after the rightmost set bit, including the rightmost set bit itself.
Decimal(n) | Binary
10 | 1010
10-1 = 9 | 1001
9-1 = 8 | 1000
8-1 = 7 | 0111
7-1 = 6 | 0110So, from this, we can understand that ~(n-1) will flip all the bits to the left of the rightmost bit of a number n.
We can now perform n & ~(n-1) to turn off all the bits of a number(n) except the rightmost set bit.
-----------------------------------------------------
Decimal | Binary
-----------------------------------------------------
(n) | (n) | (n-1) | ~(n-1) | n & ~(n-1)
-----------------------------------------------------
10 | 1010 | 1001 | 0110 | 0010
9 | 1001 | 1000 | 0111 | 0001
8 | 1000 | 0111 | 1000 | 1000
7 | 0111 | 0110 | 1001 | 0001
Let's put all this into code.
C++ Code
Time Complexity
Since we are only iterating twice through all the elements of array A, this solution's time complexity is O(n). Where n is the length of array A.
Space Complexity
Since we are using constant space, this solution's space complexity is O(1).
Hooray! We successfully solved this problem with the expected time and space complexity.
Hopefully, you enjoyed this blog post and learned something new. If you want to share anything or if you have any doubts or suggestions please comment below.
To test how much you understood this solution, I would like to ask one question.
Question: does this solution works even if array A contains exactly two elements that occur the odd number of times and rest of its elements occurs even number of time?
Let me know your answer in the comment section below.
Thank you, guys.
Have a nice day and stay tuned for new blog posts. Bye ...👋
Comments
Post a Comment