给定n-1*n数组,找到缺失的数字

Question

这里每行包含一个数字的位表示.这些数字来自1..N正好缺少一个数字.找到缺失数字的位表示.
面试官问我这个问题.
我说:"我们可以找到给定数字的总和,并从前n个数字的总和中减去它(我们知道为(N*(N + 1))/ 2)"
他说这涉及从基数10变为2.
你能否给我一个如何在不改变基础的情况下解决问题的提示？

Answer 1

您可以XOR同时从所有号码0.. N范围,然后XOR从阵列中的数字.结果将是缺少的数字.

说明: XOR一个数字本身总是导致零.XOR除了丢失的算法之外,上面的算法每个数字都是两次.缺少的数字将XOR为零,恰好为零,因此结果将等于缺失的数字.

注意:面试官在需要转换基础以进行添加时是错误的:添加二进制数字很容易也很有趣 - 事实上,计算机一直这样做:-)