In this shot, we discuss a general solution to all the problems in which we’re asked to find the unique number from an array, like a single number and a single number 2. These problems are common in coding interviews.
We are given x
, N
, and an array of x
.N
+1 numbers. Here, N
numbers occur x
times, and one unique number occurs only once. We have to find this unique number.
XOR
bitwise operatorLet x
=2, N
=3,
array
= [1, 2, 3, 3, 1, 5, 2]
In this example, {1, 2, 3} occur twice, but 5 occurs only once.
Unique Number = 5.
Let x
=5, N
=2 :
array
= [3, 3, 1, 3, 9, 3, 3, 9, 9, 9, 9]
Unique Number = 1.
It is important to note that this solution will only work if x
is even.
We use two of XOR’s properties:
This means any number’s XOR even times is equal to 0.
Now, if x
is even, the cumulative XOR of array
will give us that unique number.
array
= [1, 1, 4, 5, 4]
cumulative XOR = 1^1^4^5^4
Rearranging the order in which we perform XOR will not affect the cumulative XOR’s value because XOR is commutative.
cumulative XOR = 1^1^4^4^5
cumulative XOR = 0^0^5
cumulative XOR = 5
We have x*N+1
numbers in the array
.
setBitCounter
array such that setBitCounter[i]
= count of numbers in array
which have their ith
bit set in their binary representation.A very important observation is that every number except the
unique number
occursx
times
i
∈ [0, 64], setBitCounter[i]
will be multiple of x
, until the ith
bit of unique number
is set. This means now we know the binary representation of the answer (i.e., the unique number
) and just have to convert binary to decimal to find the unique number
.if setBitCounter[ i ]%x==0:
ith bit of unique number is not set.
else:
ith bit of unique number is set.
Here’s the input format for the code solution:
N
.x
.x
.N
+ 1 space-separated integers.number | 2nd bit | 1st bit | 0th bit |
3 | 0 | 1 | 1 |
4 | 1 | 0 | 0 |
5 | 1 | 0 | 1 |
5 | 1 | 0 | 1 |
4 | 1 | 0 | 0 |
setBitCounter | 4 | 1 | 3 |
N = int(input()) x = int(input()) # array of x*N + 1 numbers array = list(map(int,input().split())) #initializing set bit count for every bit 0 setBitCounter = [0 for j in range(64)] for i in range(64): for v in array: # ith bit of v VbitI = ((v>>i)&1) # updating ith set bit count. setBitCounter[i] += VbitI uniqueNumber = 0 for i in range(64): if setBitCounter[i]%x!=0: # this means ith bit of unique number is set # hence adding 2^i to the ans uniqueNumber += (1<<i) print(uniqueNumber)
Enter the input below
N
and x
as input.x
.N
+1 space-separated numbers as input and store them in array
.setBitCounter
as 0.i
from 0 to 64.v
of array
.VbitI
is the i
th bit of v
.setBitCounter
[ i
] if the i
th bit of v
is set.unique number
as 0.i
from 0 to 64. In line 21, we check if setBitCounter
[ i
] % x
!= 0. In line 25, we add 2^i
to the unique number
.unique number
.RELATED TAGS
CONTRIBUTOR
View all Courses