파이썬에서 정수 배열의 모든 수와 XOR 할 때 최소 합계를 제공하는 숫자 찾기

배열 A가 있다고 가정하고 (A[0] XOR X) + (A[1] XOR X) + … + A[n – 1] XOR X가 가능한 한 최소가 되도록 숫자 X를 찾아야 합니다.

따라서 입력이 [3, 4, 5, 6, 7]과 같으면 출력은 X =7, Sum =10

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• search_res() 함수를 정의합니다. arr, 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)가 0이 아니면
      • cnt :=cnt + 1
  • cnt> (n / 2)의 정수 부분이 0이 아닌 경우
    • X :=X + (2^i)
• 합계 :=0
• 0에서 n 사이의 i에 대해
  • 합계 :=합 +(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