Find missing number and duplicate number

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.

0 Thoughts on “Find missing number and duplicate number

  1. Sekar on June 17, 2015 at 10:06 am said:

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

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation