We have 2*N
+2 numbers. In this expression, every number comes twice except two numbers which occur once.
Find these two numbers.
Let two numbers that occur once be a
and b
. The array be a list of 2*N
+2 numbers.
N
=2, array
= [2, 1, 3, 5, 1, 3]
In this example, {1, 3} occur twice and {2, 5} occur once.
Thus, a
= 2 and b
= 5
N
=3, array
= [1, 10, 10, 1, 5, 6, 5, 9]
a
= 6
b
= 9
Let a
and b
be the two unique numbers.
We’ll first calculate the res and cumulative XOR of the array.
We know that the XOR of any number occurring even times is 0. Moreover, every number except a
and b
occur twice.
Thus, effectively res
= a
^b
.
Now, a fundamental observation is:
a
^ b
.Note: If the
i
th bit ofres
is set, thei
th bit ofa
and thei
th bit ofb
must be different.
We’ll split the main array into two arrays (array1
and array2
).
array1
= List of numbers of array
which have their i
th bit same as i
th bit of a
.
array2
= List of numbers of array
which have their i
th bit same as i
th bit of b
.
The cumulative XOR of array1
will give us the value of a
, and the cumulative XOR of array2
will provide us with the value of b
.
N = 3 array = [1, 10, 10, 1, 5, 6, 5, 9] a,b = 0,0 res = 0 for v in array: res = res^v lsb = 0 while (True): if ((res>>lsb)&1): break lsb+=1 for v in array: if ((v>>lsb)&1): a^=v else: b^=v print(a,b)
Line 1: We take N
as input.
Line 2: We take 2*N
+2 numbers as input and store them in an array
.
Lines 3–4: We initialize two unique numbers (a
,b
) and cumulative XOR of array
and res
to 0
.
Line 6: We loop over every value v
of the array to calculate res
.
Line 9: We initialize lsb
(the least significant bit) to 0
.
Lines 10–12: We start the while
loop to calculate lsb
of res
.
Lines 15–17: We loop over every value v
of the array
.
Line 16: If the lsb
th bit of v
is set, then we perform a = a^v
, since we want a
to be the cumulative XOR of all numbers in array with their lsb
bit set.
Line 17: If the lsb
th bit of v
is off, then b = b^v
.
Line 19: Consequently, the first unique number will be a
, and the second unique number will be b
.
RELATED TAGS
CONTRIBUTOR
View all Courses