Quickest way to find missing number in an array of numbers

0 votes
asked Jan 21, 2010 by thunderhashy

I have an array of numbers from 1 to 100 (both inclusive). The size of the array is 100. The numbers are randomly added to the array, but there is one random empty slot in the array. What is the quickest way to find that slot as well as the number that should be put in the slot? A Java solution is preferable.

30 Answers

0 votes
answered Jan 12, 2010 by ashiskumar
    //Array is shorted and if writing in C/C++ think of XOR implementations in java as follows.
                    int num=-1;
    for (int i=1; i<=100; i++){
        num =2*i;
        if(arr[num]==0){
         System.out.println("index: "+i+" Array position: "+ num);      
         break;
        }
        else if(arr[num-1]==0){
         System.out.println("index: "+i+ " Array position: "+ (num-1)); 
         break;             
        }           
    }// use Rabbit and tortoise race, move the dangling index faster, 
     //learnt from Alogithimica, Ameerpet, hyderbad**
0 votes
answered Jan 19, 2010 by tushar-gupta

I think the easiest and possibly the most efficient solution would be to loop over all entries and use a bitset to remember which numbers are set, and then test for 0 bit. The entry with the 0 bit is the missing number.

0 votes
answered Jan 21, 2010 by mick

Another homework question. A sequential search is the best that you can do. As for a Java solution, consider that an exercise for the reader. :P

0 votes
answered Jan 21, 2010 by arnkrishn

You can do this in O(n). Iterate through the array and compute the sum of all numbers. Now, sum of natural numbers from 1 to N, can be expressed as Nx(N+1)/2. In your case N=100.

Subtract the sum of the array from Nx(N+1)/2, where N=100.

That is the missing number. The empty slot can be detected during the iteration in which the sum is computed.

// will be the sum of the numbers in the array.
int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++)
{
    if (arr[i] == 0)
    {
         idx = i; 
    }
    else 
    {
         sum += arr[i];
    }
}

// the total sum of numbers between 1 and arr.length.
int total = (arr.length + 1) * arr.length / 2;

System.out.println("missing number is: " + (total - sum) + " at index " + idx);
0 votes
answered Jan 21, 2010 by jspcal

5050 - (sum of all values in the array) = missing number

int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++) {
  if (arr[i] == 0) idx = i; else sum += arr[i];
}
System.out.println("missing number is: " + (5050 - sum) + " at index " + idx);
0 votes
answered Jan 21, 2010 by giri

Quick sort is the best choice with maximum efficiency....

0 votes
answered Jan 21, 2010 by martin-booth

This is c# but it should be pretty close to what you need:

int sumNumbers = 0;
int emptySlotIndex = -1;

for (int i = 0; i < arr.length; i++)
{
  if (arr[i] == 0)
    emptySlotIndex = i;
  sumNumbers += arr[i];
}

int missingNumber = 5050 - sumNumbers;
0 votes
answered Jan 1, 2011 by mariu5

The solution that doesn't involve repetitive additions or maybe the n(n+1)/2 formula doesn't get to you at an interview time for instance.

You have to use an array of 4 ints (32 bits) or 2 ints (64 bits). Initialize the last int with (-1 & ~(1 << 31)) >> 3. (the bits that are above 100 are set to 1) Or you may set the bits above 100 using a for loop.

  1. Go through the array of numbers and set 1 for the bit position corresponding to the number (e.g. 71 would be set on the 3rd int on the 7th bit from left to right)
  2. Go through the array of 4 ints (32 bit version) or 2 ints(64 bit version)

    public int MissingNumber(int a[])
    {   
        int bits = sizeof(int) * 8;
        int i = 0;
        int no = 0;
        while(a[i] == -1)//this means a[i]'s bits are all set to 1, the numbers is not inside this 32 numbers section
        {
            no += bits;
            i++;
        }
        return no + bits - Math.Log(~a[i], 2);//apply NOT (~) operator to a[i] to invert all bits, and get a number with only one bit set (2 at the power of something)
    }

Example: (32 bit version) lets say that the missing number is 58. That means that the 26th bit (left to right) of the second integer is set to 0.

The first int is -1 (all bits are set) so, we go ahead for the second one and add to "no" the number 32. The second int is different from -1 (a bit is not set) so, by applying the NOT (~) operator to the number we get 64. The possible numbers are 2 at the power x and we may compute x by using log on base 2; in this case we get log2(64) = 6 => 32 + 32 - 6 = 58.

Hope this helps.

0 votes
answered Jan 15, 2011 by moses

If the array is randomly filled, then at the best you can do a linear search in O(n) complexity. However, we could have improved the complexity to O(log n) by divide and conquer approach similar to quick sort as pointed by giri given that the numbers were in ascending/descending order.

0 votes
answered Jan 16, 2011 by bchetty

This was an Amazon interview question and was originally answered here: 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?

It was answered, as below:

1) Calculate the sum of all numbers stored in the array of size 51. 
2) Subtract the sum from (52 * 53)/2 ---- Formula : n * (n + 1) / 2.

It was also blogged here: Software Job - Interview Question

Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...