PythonのLambda式とreduce関数で奇数回出現する数値を見つける方法

はじめに

本記事では、ユーザーが入力した正の整数の配列（リスト）の中から、奇数回出現する数値を見つける方法を解説します。PythonのLambda式とfunctools.reduce関数、そしてXOR演算を組み合わせることで、この問題を非常にシンプルなコードで解決できます。

実行例

入力 : A = [2, 4, 7, 7, 4, 2, 2]
出力 : 2

この例では、2 だけが3回（奇数回）出現しているため、結果として 2 が出力されます。

アルゴリズムの仕組み

この手法の鍵となるのは、XOR（排他的論理和 ^）演算が持つ以下の性質です。

• 同じ数同士のXORは 0 になる（例：4 ^ 4 = 0）
• 0 と任意の数のXORは、その数自身になる（例：0 ^ 7 = 7）

したがって、リスト内のすべての要素を順番にXORで畳み込んでいくと、偶数回出現する数値は互いに打ち消し合って消え、奇数回出現する数値だけが最後に残るという仕組みです。

処理の手順

1. 配列（リスト）のサイズと要素を入力する
2. Lambda式 lambda a, b: a ^ b を定義する
3. reduce 関数を使って、リスト全体を単一の値になるまで畳み込む
4. 各ステップで a ^ b の計算が行われ、結果が次の a に渡される
5. 初期値を指定しない場合、a はリストの先頭要素から始まり、b には2番目以降の要素が順番に代入される

サンプルコード

# 奇数回出現する数値を見つけるPythonプログラム
# Lambda式とreduce関数を使用

from functools import reduce

def timeoccurrance(inp):
    print("RESULT ::>", reduce(lambda a, b: a ^ b, inp))

# ドライバープログラム
if __name__ == "__main__":
    A = list()
    n1 = int(input("Enter the size of the List ::"))

    print("Enter the Element of List ::")
    for i in range(n1):
        k = int(input())
        A.append(k)

timeoccurrance(A)

実行結果

Enter the size of the List :: 7
Enter the Element of List ::
1
2
3
2
3
1
3
RESULT ::> 3

この例では、1 と 2 はそれぞれ2回（偶数回）出現するためXOR演算で打ち消され、3回（奇数回）出現している 3 のみが結果として出力されます。

まとめ

Lambda式とreduce関数を組み合わせれば、ループや辞書（カウンター）を使わずに1行でこの問題を解決できます。計算量は O(n)、追加メモリもほぼ不要（O(1)）のため、パフォーマンス面でも非常に優れたアプローチです。ビット演算の特性を活かしたテクニックとして、競技プログラミングやコーディング面接でも頻出の話題なので、ぜひ覚えておきましょう。