Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

bit manipulation
xor
communitycreator

How to solve unique number problems

Armaan Nougai

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.

Problem statement

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.

Prerequisites

Problem explanation

Let 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.

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:

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

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

  1. 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.
array = [ 3, 4, 5, 5, 4 ]

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

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.

RELATED TAGS

bit manipulation
xor
communitycreator
RELATED COURSES

View all Courses

Keep Exploring