Quickest way to find missing number in an array of numbers

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

(sum of 1 to n) - (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);

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.

Here program take time complexity is O(logn) and space complexity O(logn)

public class helper1 {

public static void main(String[] args) {


    int a[] = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12};


    int k = missing(a, 0, a.length);
    System.out.println(k);
}

public static int missing(int[] a, int f, int l) {


    int mid = (l + f) / 2;

    //if first index reached last then no element found 
    if (a.length - 1 == f) {
        System.out.println("missing not find ");
        return 0;
    }

    //if mid with first found 
    if (mid == f) {
        System.out.println(a[mid] + 1);
        return a[mid] + 1;
    }

    if ((mid + 1) == a[mid])
        return missing(a, mid, l);
    else
        return missing(a, f, mid);

  }
 }

public class MissingNumber {

public static void main(String[] args) {
     int array[] = {1,2,3,4,6};
     int x1 = getMissingNumber(array,6);
    System.out.println("The Missing number is: "+x1);


}
private static int getMissingNumber(int[] array, int i) {

    int acctualnumber =0;
    int expectednumber = (i*(i+1)/2);

    for (int j : array) {
        acctualnumber = acctualnumber+j;

    }
    System.out.println(acctualnumber);
    System.out.println(expectednumber);
    return expectednumber-acctualnumber;

}
}

    //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**

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

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