Quickest way to find missing number in an array of numbers

Question

I have an array of numbers from 1 to 100 (both included). The size of the array is 100. The numbers are randomly filled in the array but there is one random slot empty 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.

Answer 1

1. qsort array
2. Iterate until gap

Answer 2

If it's a completely random slot, all you can do is a simple O(n) sequential search, which will result in 100 comparison in the worst case, and 50 on average.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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;

Answer 8

The formula missing number = sum - (n * (n+1)/2 ) works, is there way to do this with bit operators

Answer 9

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.