How to solve unique number problems

Overview

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.

Solution approach 1

It is important to note that this solution will only work if x is even.

We use two of XOR’s properties:

a^a = 0. Also a^a^a^a = 0

This means any number’s XOR even times is equal to 0.

a^c^a^b^c = b.

Now, if x is even, the cumulative XOR of array will give us that unique number.

Example

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

Solution approach 2

We have x*N+1 numbers in the array.

First we make the 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 occurs x times

For every 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.

Explanation

Here’s the input format for the code solution:

Line 1: This contains an integer N.

Line 2: This contains an integer x.

Line 3: This contains x.N + 1 space-separated integers.

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

Code input area

Code explanation

Line 1 and 2: We take N and x as input.

Line 3: We take x.N+1 space-separated numbers as input and store them in array.

Line 8: We initialize all 64 indexes of setBitCounter as 0.

Line 10-17: We start a loop for i from 0 to 64.

Line 11-17: We loop over every value, v of array.

Line 14: Here VbitI is the ith bit of v.

Line 17: We update setBitCounter[ i ] if the ith bit of v is set.

Line 19: We initialize the required unique number as 0.

Line 20-25: We start the loop for 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.

Line 27: We print the unique number.

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

How to solve unique number problems

Overview

Problem statement

Prerequisites

Problem explanation

Solution approach 1

Example

Solution approach 2

Explanation

array = [ 3, 4, 5, 5, 4 ]

Code explanation