番号と値を全部 XOR でまとめ、0 から n の中で抜けた数を見つける

ビット操作問題 155

0 から n までの n + 1 個の数のうち、1 つだけが抜けた長さ n の並びから、抜けた数を返します。0 から n の番号と並びの値を全部 XOR でまとめれば、そろった数は打ち消し合って抜けた数だけが残る練習です。

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

問題

イベントの受付で、0 から n までの整理券を 1 枚ずつ配りました。回収した整理券の番号が、長さ n の並び nums で渡されます。n + 1 枚のうち 1 枚だけが戻っていません。戻っていない番号を返す関数を書いてください。

nums の値はどれも 0 以上 n 以下で、同じ値は 2 回出てきません。並び順はばらばらです
時間は O(n)、追加の記憶は O(1) を目指してください
n は 1 以上 10000 以下です

入力と出力の例

例 1

0 から 5 のうち、2 がありません。

nums = [4, 0, 5, 1, 3]

例 2

いちばん大きい n が抜けることもあります。0 から 4 のうち、4 がありません。

nums = [2, 3, 0, 1]

例 3

0 が抜けることもあります。

nums = [1]

面接での聞かれ方

面接では、短い問題に何通りもの解き方がある問題として出されます。

「0 から n のうち、抜けている 1 つの数を返してください」
集合や並べ替えの書き方を見せると、「追加の記憶 O(1)、時間 O(n) でできますか？」と続きます
和で解く書き方を見せると、「n がとても大きいと、和はあふれませんか？」と聞かれることがあります

いくつかの書き方を比べ、それぞれの弱いところを言えるかが見られています。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

まずは素直に、値を集合に入れ、0 から n まで順に集合にあるかを調べます。時間は O(n) ですが、記憶も O(n) 使います。並べ替えて i 番目が i でない所を探す書き方は、記憶は減らせても時間が O(n log n) です。

段 2

0 から n の和 n(n + 1) / 2 から、並びの和を引けば抜けた数が出ます。時間は O(n)、記憶は O(1) です。ただ、32 ビットの整数しか無い言語では、n が大きいと和があふれる心配があります。

段 3

XOR を使えば、あふれを気にせず同じことができます。同じ数どうしの XOR は 0 です。0 から n までの番号と、並びの値を全部 XOR でまとめると、両方に出てくる数は打ち消し合い、番号にだけある抜けた数が残ります。並びの添え字 i (0 から n - 1) を番号に使い、最後に n を足せば、0 から n がそろいます。

解答

Python

def missing_number(nums):
    n = len(nums)
    acc = n
    for i, v in enumerate(nums):
        acc ^= i ^ v
    return acc

JavaScript

function missingNumber(nums) {
  const n = nums.length;
  let acc = n;
  for (let i = 0; i < n; i++) {
    acc ^= i ^ nums[i];
  }
  return acc;
}

Go

func missingNumber(nums []int) int {
	n := len(nums)
	acc := n
	for i, v := range nums {
		acc ^= i ^ v
	}
	return acc
}

acc を n から始めているのが、番号の最後の n の分です。

計算量

時間は O(n) です。並びを 1 回なめます
追加の記憶は O(1) です
和で解く書き方も時間 O(n)、記憶 O(1) です。この問題の n の範囲なら和はあふれませんが、XOR はどんな大きさでもあふれません

よくある間違い

n の分を足し忘れる。添え字は 0 から n - 1 までなので、acc を 0 から始めると番号 n が入りません。例 2 で、抜けた 4 の代わりに 0 を返してしまいます
並びが並べ替え済みだと思い込む。例 1 のように並びはばらばらです。「i 番目が i でない所」を探す書き方は、並べ替えてからでないと使えません
和の書き方であふれを無視する。 n が 10 万を超える場面で、32 ビットの整数で n(n + 1) を先に計算すると、あふれて答えが狂います

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

main.py

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

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

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

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


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

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