全部を XOR でまとめ、1 回だけ出てくる値を見つける

ビット操作問題 151

1 つを除いてどの値もちょうど 2 回ずつ出てくる並びから、1 回だけ出てくる値を返します。同じ値どうしの XOR は 0 になるので、全部を XOR でまとめれば対の値が消えて 1 つだけ残る練習です。

海外で定番の問題リスト 4 本には入っていません

問題

靴の倉庫で、左右の対になった靴に同じ番号を振っています。番号の並び nums を受け取ります。1 つの番号を除き、どの番号もちょうど 2 回ずつ出てきます。片方しか無い靴の番号、つまり 1 回だけ出てくる値を返す関数を書いてください。

時間は O(n)、追加の記憶は O(1) を目指してください
nums の長さは 1 以上 30000 以下の奇数、値はどれも -30000 以上 30000 以下です

入力と出力の例

例 1

nums = [7, 3, 5, 3, 7]

例 2

並びが 1 つだけなら、その値が答えです。

nums = [12]

例 3

負の数と 0 も入ります。

nums = [-4, 0, 9, -4, 9]

面接での聞かれ方

面接では、ビット演算の入り口として短く出されることが多い問題です。

「1 つだけ対になっていない数を返してください」
辞書で数える書き方を見せると、「追加の記憶を使わずにできますか？」と続きます
「3 回ずつ出てくる中から 1 つを探すなら？」と、続きを聞かれることもあります

XOR の性質を知っていて、それを理由とともに説明できるかが見られています。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

まずは素直に、値ごとの出てきた回数を辞書に数え、1 回の値を返す書き方を考えます。時間は O(n) ですが、記憶も O(n) 使います。

段 2

XOR (排他的論理和) は、ビットごとに「違えば 1、同じなら 0」にする演算です。同じ値どうしの XOR は 0、どの値も 0 との XOR はその値のまま、そして順番を入れ替えても結果は変わりません。

段 3

並びの全部の値を XOR でまとめると、順番を入れ替えて対の値どうしを先に XOR したのと同じになります。対はどれも 0 に消え、残るのは 1 回だけの値と 0 の XOR、つまりその値そのものです。

解答

Python

def single_number(nums):
    acc = 0
    for v in nums:
        acc ^= v
    return acc

JavaScript

function singleNumber(nums) {
  let acc = 0;
  for (const v of nums) {
    acc ^= v;
  }
  return acc;
}

Go

func singleNumber(nums []int) int {
	acc := 0
	for _, v := range nums {
		acc ^= v
	}
	return acc
}

負の数も 2 の補数のビットで XOR されるので、そのまま正しく打ち消し合います。

計算量

時間は O(n) です。並びを 1 回なめます
追加の記憶は O(1) です。acc だけです
辞書で数える書き方は時間は同じ O(n) で、記憶が O(n) になります。並べ替えて隣どうしを比べる書き方は、記憶を減らせても時間が O(n log n) です

よくある間違い

全部を足して引く。「違う値の和の 2 倍から全部の和を引く」書き方は、違う値を集める集合に O(n) の記憶が要ります
並べ替えて 2 つずつ比べ、末尾を見落とす。並べ替えると対が隣どうしに並びますが、1 回だけの値がいちばん大きいと末尾に残り、比べる相手がいません。ループの後で末尾を返し忘れがちで、時間も O(n log n) に増えます
XOR と累乗を取り違える。言語によって ^ の意味が違います。Python、JavaScript、Go の ^ は XOR ですが、数式の累乗のつもりで読まないよう、面接では「XOR です」と口に出します

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def single_number(nums: list[int]) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(single_number([7, 3, 5, 3, 7]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します