題目：數組A中包含n-1個[0,n-1]內的不同整數，n個數中只有一個數不在所給的數組中。設計一個找到這個數的O(n)時間的算法。除了數組A自身以外，只能利用O(1)的額外空間。

與之相似的另一個題目見《算法導論》思考題4-2：問題同上，但在這里，不能由一個單一操作來訪問A中的一個完整整數，因為A中整數是以二進制表示的。我們所能用的唯一操作就是“取A[i]的第j位”，這個操作所花時間為常數。題目要求：證明如果僅用此操作，仍能在O(n)時間內找出所缺整數。

第一個題目可以想出以下幾種方法：

解法一：[0,n-1]這個區間中所有整數的和不變，為n*(n-1)/2，對數組A中的所有元素求和，設為s，則丟失的整數就是n*(n-1)/2 – s。

解法二：異或運算。異或是個非常神奇的運算。設所缺的整數為k，[0,n-1]區間中所有n個數的異或結果為s(n)，異或運算滿足交換率和結合率，所以s(n)可以被看作[0,n-1]中去掉k外的另外n-1個數的異或結果s(n-1)和k的異或。也即：s(n)=s(n-1)^k，我們給等式兩邊同時異或s(n-1)，等式變成了：s(n-1)^s(n)=s(n-1)^s(n-1)^k=k。而且，很明顯s(n-1)其實就是數組A中所有元素的異或。所以，解法二就是：求出[0,n-1]內所有整數的異或結果s，再求出數組A中所有元素的異或結果t，所缺的整數就是s異或t。

解法三：因為A自身也有n-1個位置。可以把A作為一個散列表，這樣做雖然能夠得到結果，但是破壞了數組A。

至于《算法導論》思考題4-2的解法，在《算法藝術與信息學競賽》上有解答。思路簡述：自然數順序的二進制表示最低位總是0和1交替出現，所以，首先讀取數組A中所有元素的最低二進制位，如果得到的0和1的個數一樣多，則說明所缺整數的最低二進制位為0，否則，哪個少，所缺整數的最低二進制位就是哪個。比如，我們得到所缺整數的最低二進制位為0，那么，說明數組A中最低二進制位為1的那些整數已經與此題無干，只需要在那些最低位為0的整數中找所缺整數。所以，時間復雜度是：T(n)=T(n/2)+n，計算：

對n的上取整或下取整不影響時間復雜度。即T(n)=O(n)。