空間計算量O(1)で配列内のユニークな数字を見つけるBit Manipulation: Lonely Integer

問題

n個の要素(整数)の配列が与えらる。配列内の要素はただ１つを除いて、全て２回ずつ現れる。１回のみ出現するユニークな数字を求める問題。

www.hackerrank.com

解法

この問題は、XORを用いることで空間計算量O(1)で解くことができる。

上記のように配列内の全ての要素をXORすることでユニークな値を見つけることができる。これにはXORの以下の性質があるからだ。

a) どんな数字でも自分自身とXORを取ると０になる。
b) どんな数字でも０とXORを取るとその数字自身になる。

今回の問題では、１つを除いて配列内の数字は同じ数字がちょうど２回出現する。もし、配列内の全ての数字がちょうど２回ずつ出現するとしたら、それらのXORは０となる。実際には１つだけ出現回数が１回のものがあるので、０とユニークな数字をXORすると、そのユニークな数字が得られる。