Given an array of size N containing number from 1 to n,except one number is missing and one number is duplicated.Find Both numbers in linear time.

This problem is an extension of our post of finding missing number in an array.

**Solution** : Let missing number be x and duplicate number be y. We know that sum of of numbers from 1 to n is n*(n+1)/2. we can scan all numbers of array in O(n) time and get the sum of all numbers. This sum would be:

S= n*(n+1)/2-x+y;

We also know the sum of squares of first n numbers is n*(n+1)*(2n+1)/6. Now we calculate the sum of squares of elements in the array, which would sum up to

S2 = n*(n+1)*(2n+1)/6 – x^2+y^2;

We have got two equations and two unknown variables x and y.We can solve the equations and find the value of x and y.

The above solution many not work, if the array length is more. ex. if the length is 1000000000.

My simple solution is, assuming array is sorted.

int x = 0;

int y = 0;

int A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 8, 10 };

for (int i = 0; i < A.length; i++) {

if (A[i] != i + 1) {

y = i + 1;

x = A[i];

}

}

System.out.println("x=" + x + ",y=" + y);