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