Pythonで整数の配列のすべての数とXORするときに最小の合計を与える数を見つけます

配列Aがあるとすると、（A [0] XOR X）+（A [1] XOR X）+…+ A [n – 1]XORXが可能な限り最小になるような数Xを見つける必要があります。

したがって、入力が[3、4、5、6、7]の場合、出力はX =7、Sum =10

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

• 関数search_res（）を定義します。これには時間がかかります、n
• 要素：=arr [0]
• 0からarrのサイズまでの範囲のiについては、
  • arr [i]>要素の場合、
    • 要素：=arr [i]
• p：=（要素の底2の対数）+1の整数
• X：=0
• 0からpの範囲のiについては、
  • cnt：=0
  • 0からnの範囲のjについては、
    • arr [j] AND（2 ^ i）がゼロ以外の場合、
      • cnt：=cnt + 1
  • cnt>（n / 2）の整数部分がゼロ以外の場合、
    • X：=X +（2 ^ i）
• 合計：=0
• 0からnの範囲のiについては、
  • sum：=sum +（X XOR arr [i]）
• Xと合計を返す

例

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

from math import log2
def search_res(arr, n):
   element = arr[0]
   for i in range(len(arr)):
      if(arr[i] > element):
         element = arr[i]
   p = int(log2(element)) + 1
   X = 0
   for i in range(p):
      cnt = 0
      for j in range(n):
         if (arr[j] & (1 << i)):
            cnt += 1
      if (cnt > int(n / 2)):
         X += 1 << i
   sum = 0
   for i in range(n):
      sum += (X ^ arr[i])
   print("X =", X, ", Sum =", sum)
arr = [3, 4, 5, 6, 7]
n = len(arr)
search_res(arr, n)

入力

[3, 4, 5, 6, 7]

出力

X = 7 , Sum = 10