Pythonで配列の全要素のXOR（排他的論理和）を計算するプログラム

問題概要

整数 n と整数 start が与えられます。ここで、nums[i] = start + 2*i（i は 0 から開始）という規則に従う配列 nums を作成します。配列のサイズは n です。そして、配列内のすべての要素のビットごとの XOR（排他的論理和）を求めます。

たとえば、入力が n = 6、start = 2 の場合、出力は 14 になります。配列は [2+2*0, 2+2*1, ... , 2+2*5]、すなわち [2, 4, 6, 8, 10, 12] となり、これらの要素すべてを XOR すると 14 になるためです。

解き方の手順

この問題を解くには、次の手順に従います。

• 変数 count を start で初期化する
• n - 1 > 0 の間、以下を繰り返す
  • count := count XOR (2 + start)
  • n := n - 1
  • start := start + 2
• count を返す

このアプローチでは、ループの各ステップで「前回の start より 2 大きい値」を count に XOR していくため、配列を実際に生成することなく結果を求められます。計算量は O(n)、追加のメモリは O(1) で済むのがポイントです。

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

def solve(n, start):
    count = start
    while n-1 > 0:
        count ^= 2 + start
        n -= 1
        start += 2
    return count

n = 6
start = 2
print(solve(n, start))

入力

6, 2

出力

14

処理の流れを確認

n = 6、start = 2 の場合、ループは 5 回実行され、次のように計算が進みます。

• 初回：count = 2（配列の最初の要素）
• 2 回目以降：2, 4, 6, 8, 10, 12 を順番に XOR していき、最終的に 14 が得られる

まとめ

このように、配列を明示的に構築しなくても、while ループと XOR 演算子（^）を組み合わせることで、等差数列的な要素を持つ配列全体の XOR をシンプルかつ効率的に計算できます。ビット演算の基礎を固める練習問題として、ぜひ実際にコードを動かして挙動を確かめてみてください。