Matsushita's Blog

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

問題

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

www.hackerrank.com

解法

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

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

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

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