这里每行包含一个数字的位表示 . 这些数字来自1..N正好缺少一个数字 . 找到缺失数字的位表示 .面试官问我这个问题 .我说："We can find the sum of the given numbers and subtract it from the sum of first n numbers(which we know as (N*(N+1))/2)"他说，涉及从基地10改为基地2 .你能否告诉我如何在不改变基础的情况下解决问题？
你可以 XOR 一起 0 .. N 范围内的所有数字，然后 XOR 数组中的数字 . 结果将是缺少的数字 .
XOR
0
N
Explanation: XOR 一个数字本身总是导致零 . 上面的算法 XOR s每个数字正好两次，除了缺少的一个 . 丢失的数字将是 XOR -ed，零恰好一次，因此结果将等于缺失的数字 .
注意：面试官在需要转换基础以进行添加时是错误的：添加二进制数字很容易也很有趣 - 事实上，计算机一直都在这样做:-)
你可以将这些数字混合在一起，并将XOR与1..n进行异或 . 数字以二进制形式存储的事实是一个很好的提示，BTW .
实际上，任何具有逆运算的交换运算符都应该有效，因为如果运算符是可交换的，则顺序无关紧要，因此它可以应用于您拥有的数字和1..n，差别是第一个不是对不在阵列中的数字进行操作 . 然后你可以使用它的逆来找到那个数字，你有两个结果 . SO + 和 - ， * 和 / ， XOR 和 XOR 以及符合要求的任何其他运营商都应该在这里工作 .
+
-
*
/
2 回答
你可以
XOR一起0..N范围内的所有数字，然后XOR数组中的数字 . 结果将是缺少的数字 .Explanation:
XOR一个数字本身总是导致零 . 上面的算法XORs每个数字正好两次，除了缺少的一个 . 丢失的数字将是XOR-ed，零恰好一次，因此结果将等于缺失的数字 .注意：面试官在需要转换基础以进行添加时是错误的：添加二进制数字很容易也很有趣 - 事实上，计算机一直都在这样做:-)
你可以将这些数字混合在一起，并将XOR与1..n进行异或 . 数字以二进制形式存储的事实是一个很好的提示，BTW .
实际上，任何具有逆运算的交换运算符都应该有效，因为如果运算符是可交换的，则顺序无关紧要，因此它可以应用于您拥有的数字和1..n，差别是第一个不是对不在阵列中的数字进行操作 . 然后你可以使用它的逆来找到那个数字，你有两个结果 . SO
+和-，*和/，XOR和XOR以及符合要求的任何其他运营商都应该在这里工作 .