問題
配列の中で、他の数字は全て2つずつある中で、唯一1つだけの数字を見つけなさい。
例えば、[1, 2, 3, 3, 1, 2, 4]という配列であれば、4が答えになります。
解説
Single Number Problemという有名な問題で、ベストな解き方は、XORを使います。
Find the element that appears once in an array where every other element appears twice
確かにそうなるけど、へーって思いました。
[1, 2, 3, 3, 1, 2, 4] で考えると、
1 ^ 2 ^ 3 ^ 3 ^ 1 ^ 2 ^ 4 = (1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 3) ^ 4 = 4
と、4が答えになります。
Pythonで書くと、以下のようになります。
nums = [1, 2, 3, 3, 1, 2, 4]
ans = 0
for i in range(len(nums)):
ans ^= nums[i]
print(ans)