Interview Question for Software Engineer at Google:

The answer is relatively simple and requires linear space and linear time, which in this case is number of numbers to be assessed. Additionally, this solution works for both one and more than one missing numbers. (Note: there is no error checking...)

public static void findremoved(int[] input) {
      HashSet<Integer> s = new HashSet<Integer>();
      for(int i = 1; i <= 100; i++) s.add(i);
      for(int i = 0; i < input.length; i++)
        s.remove(input[i]);
      for(int e : s)
        System.out.println(e);
    }

Constant space and linear time:

def missing_num(numbers):
    s = len(numbers) + 1
    for i, num in enumerate(numbers):
        s += i+1
        s -= num
    return s

numbers = range(1, 101)
numbers.remove(89)
random.shuffle(numbers)
print missing_num(numbers)

sum = 0;
n = 100;
for( i =1; i <= n; i++)
       sum += array[i];

print( (n+(n+1)/2 ) - sum )

you meant print( (n*(n+1)/2 ) - sum )