We can solve it using O(n) also as we know the number range [1 - 100]

Let me give mathematics behind to solve this problem

1 2 3 4 5 - Actual array should look like this

But instead one is duplicate , but the array numner is 1-100 , so any way a number will be missing where duplicate element is present.

So two scenario possible

**Case 1:**

1,2 ,3, 4, 4 - Here **5 is missing and 4 is repeated**

**Case 2:**

1,2,3,5, 5 - Here **4 is missing and 5 is repeated**

So consider x as missing number and y as repeated number.

So

In case1 , x = 5 is missing and y = 4 is repeated **so here x > y**

in case 2 , x = 4 is missing and y = 5 is repeated **so here y > x**

Consider total member in the array **N = 5**

So for ideal case (No duplicate and no missing) [1, 2, ,3, 4, 5] then **sum is N * (N +1) / 2**

So total sum is 5 * 6 / 2 = 15

But in case of

case 1 : [1,2 ,3, 4, 4 ] Sum of all number is 14

case 2 : [1,2,3,5,5] Sum of all member is 16

**Logic 1**

SUM(ideal) = 1+2+3+4+5 = 15

SUM(case1 ) = 1+2+3+4+4 = 14

SUM(case2 ) = 1+2+3+5+5 = 16

So conclusion

**SUM(Ideal) = SUM(case1) + X - Y**

SUM(Ideal) = SUM(case2) + X - Y

Because X is missing and Y is repeated

**To get X-Y = SUM(Ideal) - SUM(Given array)**

Given array can be any type it may lie in case 1 or case 2.

So now we have two variable and one equation if we will get another equation we can know x and y both, so we can find duplicate number.

**Logic 2**

we may be aware of this formula

1^2 + 2 ^2 + 3^2 + 4^2 + 5 ^2 .+ .... + N^2 = N* (N + 1) * (2N + 1) / 6;

This will be the ideal series

Ideal case 1^2 + 2 ^2 + 3^2 + 4^2 + 5 ^2 = 55

case 1: - 1^2 + 2 ^2 + 3^2 + 4^2 + 4 ^2 = 46 (x > y)

case 2:- 1^2 + 2 ^2 + 3^2 + 5^2 + 5 ^2 = 64 (y > x)

So

**SQUARE_SUM(Ideal) = SQUARE_SUM(case1) + X^2 - Y ^2**

SQUARE_SUM(Ideal) = SQUARE_SUM(case2) + X^2 - Y ^ 2

Because X is missing and Y is repeated

**To get X^2 - Y^2 = SQUARE_SUM(Ideal) - SQUARE_SUM(Given array)**

So now we know X^2 - Y ^ 2 and X- Y also , now we can find X and Y so solution done :-)