Question

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

Answer 1

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 :-)

Comments

Amazing theory! thanks for sharing

Answer 2

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[100];

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]));
    }
}

Comments

//For me this gives ans even the number repeated multiple times. Don't mind this is Java code :)
//Change: added break.

    int array[] = new int[1001];
   
    for (int i = 0; i <= 1000; i++)
    {
        array[i] = i;
    }
   
    array[8] = 3;
    array[10] = 3;
    array[464] = 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;
            }
        }
    }