   # In an integer array, there is 1 to 100 number, out of one is duplicate, how to find ?

908 views
In an integer array, there is 1 to 100 number, out of one is duplicate, how to find ? posted Aug 7, 2015

+1 vote

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 :-) answer Aug 13, 2015
Amazing theory! thanks for sharing

You can achieve it by many methods,
Here, I am doing this with for loop, I don't know whether this is best way, but this will help,

lets say you have an integer array of 100 variable, i.e. int array;

``````for(i=0;i<99;i++)
{
for(j=i+1;j<100;j++)
{
if(a[i]==a[j])
printf("%d is duplicate in array\n",a[i]));
}
}
`````` answer Aug 8, 2015
//For me this gives ans even the number repeated multiple times. Don't mind this is Java code :)

int array[] = new int;

for (int i = 0; i <= 1000; i++)
{
array[i] = i;
}

array = 3;
array = 3;
array = 3;

for(int i=0;i<array.length-1;i++)
{
for(int j=i+1;j<array.length;j++)
{
if(array[i]==array[j])
{
System.out.println(array[i]+" is duplicate element in array at index "+ j);
break;
}
}
}
Similar Questions
+1 vote

For eg. 1,4,6,7,3,1,4,7,3,1,6 (given array)

+1 vote

Given an array of 1s and 0s which has all 1s first followed by all 0s. Find the number of 0s. Count the number of zeroes in the given array.