试着找出从1到50的数的乘积:

令product, P1 = 1 × 2 × 3 × .............50

当你一个一个地把数提出来，把它们相乘，就得到乘积P2。但是这里少了两个数字，因此P2 < P1。

这两项的乘积，a x b = P1 - P2。

你已经知道这个和了，a + b = S1。

由上述两个方程，用二次方程求解a和b。A和b是你缺失的数。

试着找出从1到50的数的乘积:

令product, P1 = 1 × 2 × 3 × .............50

当你一个一个地把数提出来，把它们相乘，就得到乘积P2。但是这里少了两个数字，因此P2 < P1。

这两项的乘积，a x b = P1 - P2。

你已经知道这个和了，a + b = S1。

由上述两个方程，用二次方程求解a和b。A和b是你缺失的数。

也许这个算法可以解决问题1:

预计算前100个整数的xor (val=1^2^3^4....100) 对来自输入流的元素进行Xor (val1=val1^next_input) 最终的答案= val ^ val1

或者更好:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

这个算法实际上可以扩展到两个缺失的数字。第一步还是一样。当我们调用缺少两个数字的GetValue时，结果将是a1^a2是缺少的两个数字。让说

跌倒 = a1^a2

Now to sieve out a1 and a2 from val we take any set bit in val. Lets say the ith bit is set in val. That means that a1 and a2 have different parity at ith bit position. Now we do another iteration on the original array and keep two xor values. One for the numbers which have the ith bit set and other which doesn't have the ith bit set. We now have two buckets of numbers, and its guranteed that a1 and a2 will lie in different buckets. Now repeat the same what we did for finding one missing element on each of the bucket.

正如@j_random_hacker所指出的，这与在O(n)个时间和O(1)个空间中寻找重复项非常相似，我的答案在这里也适用。

假设“袋子”由一个大小为N - k的基于1的数组a[]表示，我们可以在O(N)个时间和O(k)个额外空间内求解Qk。

首先，我们将数组A[]扩展k个元素，使它现在的大小为n，这是O(k)个额外空间。然后我们运行以下伪代码算法:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

第一个循环初始化k个额外的条目，使其与数组中的第一个条目相同(这只是我们知道数组中已经存在的一个方便的值——在这一步之后，大小为N-k的初始数组中缺失的任何条目在扩展数组中仍然缺失)。

第二个循环排列扩展数组，如果元素x至少出现一次，那么其中一个元素将位于位置A[x]。

注意，尽管它有一个嵌套循环，但它仍然在O(N)时间内运行——只有当有一个i使a [i] != i时才会发生交换，并且每次交换设置至少一个元素使a [i] == i，而以前不是这样的。这意味着交换的总数(因此while循环体的执行总数)最多为N-1。

第三个循环打印数组i中没有被值i占用的索引——这意味着i一定是缺失的。

我会用另一种方法来回答这个问题，询问面试官关于他试图解决的更大问题的更多细节。根据问题和围绕它的需求，显而易见的基于集的解决方案可能是正确的，而生成一个列表然后从中挑选的方法可能不是。

For example, it might be that the interviewer is going to dispatch n messages and needs to know the k that didn't result in a reply and needs to know it in as little wall clock time as possible after the n-kth reply arrives. Let's also say that the message channel's nature is such that even running at full bore, there's enough time to do some processing between messages without having any impact on how long it takes to produce the end result after the last reply arrives. That time can be put to use inserting some identifying facet of each sent message into a set and deleting it as each corresponding reply arrives. Once the last reply has arrived, the only thing to be done is to remove its identifier from the set, which in typical implementations takes O(log k+1). After that, the set contains the list of k missing elements and there's no additional processing to be done.

这当然不是批处理预先生成的数字袋的最快方法，因为整个过程运行O((log 1 + log 2 +…)+ log n) + (log n + log n-1 +…+ log k))。但它确实适用于任何k值(即使它事先不知道)，在上面的例子中，它的应用方式使最关键的区间最小化。

我使用Java 8和Java 8之前的版本编写代码。 它使用一个公式:(N*(N+1))/2作为所有数字的和。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

   /**
 * 
 * 
 * @author pradeep
 * 
 *         Answer : SumOfAllNumbers-SumOfPresentNumbers=Missing Number;
 * 
 *         To GET SumOfAllNumbers : Get the highest number (N) by checking the
 *         length. and use the formula (N*(N+1))/2
 * 
 *         To GET SumOfPresentNumbers: iterate and add it
 * 
 * 
 */
public class FindMissingNumber {
    /**
     * Before Java 8
     * 
     * @param numbers
     * @return
     */
    public static int missingNumber(List<Integer> numbers) {
        int sumOfPresentNumbers = 0;
        for (Integer integer : numbers) {
            sumOfPresentNumbers = sumOfPresentNumbers + integer;
        }
        int n = numbers.size();
        int sumOfAllNumbers = (n * (n + 1)) / 2;
        return sumOfAllNumbers - sumOfPresentNumbers;
    }
    /**
     * Using Java 8 . mapToInt & sum using streams.
     * 
     * @param numbers
     * @return
     */
    public static int missingNumberJava8(List<Integer> numbers) {
        int sumOfPresentNumbers = numbers.stream().mapToInt(i -> i).sum();
        int n = numbers.size();
        int sumOfAllNumbers = (n * (n + 1)) / 2;
        return sumOfAllNumbers - sumOfPresentNumbers;
    }
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list = Arrays.asList(0, 1, 2, 4);
        System.out.println("Missing number is :  " + missingNumber(list));
        System.out.println("Missing number using Java 8 is : " + missingNumberJava8(list));
    }
}*