Missing Number

Apart from a few programming puzzles, I never really got to work extensively on 'Bit Array' operations. So, as was practicing a bit, I got an idea for a problem, for which I posted a solution already (Software Job - Interview Question). This problem is about finding the missing number, in a array of unsorted numbers. For Ex: We have numbers from 1 to 52 that are put into a 51 number array, what's the best way to find out which number is missing?

As per the idea in that earlier post, the code would look like:



An other solution is to use Java's BitSet, as in the below listed code. Also, note that the following logic is also good for finding multiple missing numbers. So, the below code is a better approach to find one or more than one missing numbers:

1 comment:

  1. "You can find out the missing number in array by following algorithm:

    /* getMissingNumber takes array and size of array as arguments*/
    int getMissingNumber (int arr[], int num)
    {
    int i;
    /* For xor of all the elemets in arary */
    int x1 = a[0];
    /* For xor of all the elemets from 1 to n+1 */
    int x2 = 1;

    for (i = 1; i< n; i++)
    x1 = x1^a[i];

    for ( i = 2; i <= n+1; i++)
    x2 = x2^i;

    return (x1^x2);
    }

    I also found some more possible solutions. you can check out below link for more solutions:

    Find out missing number in an array in java

    ReplyDelete

Note: Only a member of this blog may post a comment.