Pythonの各クエリの最大XORを見つけるプログラム

サイズnのnumsと呼ばれる事前に並べ替えられた配列があり、値bも1つあるとします。次のクエリをn回実行します-

• numsおよびkのすべての要素のXORが最大になるように、非負の値k <2^mを検索します。したがって、kはi番目のクエリに対する答えです。

• 現在の配列番号から最後の要素を削除します。

• 配列の回答を見つける必要があります。ここで、answer[i]はi番目のクエリに対する回答です。

したがって、入力がnums =[0,1,1,3]、m =2の場合、出力は[0,3,2,3]になります。これは、

• nums =[0,1,1,3]、k =0（0 XOR 1 XOR 1 XOR 3 XOR 0 =3であるため）

• nums =[0,1,1]、k =3（0 XOR 1 XOR 1 XOR 3 =3であるため）

• nums =[0,1]、k =2（0 XOR 1 XOR 2 =3であるため）

• nums =[0]、0 XOR 3=3であるためk=3

これを解決するには、次の手順に従います-

• x：=2 ^ m-1

• 0からnums-1のサイズのiの場合、実行します

  • nums [i]：=nums [i] XOR x

  • x：=nums [i]

• 逆転後にnumsを返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(nums, m):
   x=2**m-1
   for i in range(len(nums)):
      nums[i]^= x
      x = nums[i]
   return(nums[::-1])

nums = [0,1,1,3]
m = 2
print(solve(nums, m))

入力

[0,1,1,3], 2

出力

[0, 3, 2, 3]