# Quickest way to find missing number in an array of numbers

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.

``````    //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,
``````

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.

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

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

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

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

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

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.

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.

``````1) Calculate the sum of all numbers stored in the array of size 51.