पायथन में XOR योग न्यूनतम करने वाली संख्या ढूंढना

समस्या विवरण

सरणी A दी गई है, एक संख्या X ढूंढें जिससे Σ(A[i] XOR X) न्यूनतम हो।

उदाहरण

इनपुट: [3, 4, 5, 6, 7]

आउटपुट: X = 7, Sum = 10

एल्गोरिदम (बिटवाइज़ बहुमत)

1. सरणी में अधिकतम तत्व element ढूंढें
2. p = floor(log2(element)) + 1 (बिट्स की संख्या)
3. X = 0
4. प्रत्येक बिट पोजीशन i (0 से p-1) के लिए:
   • गिनें कितने तत्वों में i-th बिट सेट है (cnt)
   • यदि n/2: X में i-th बिट सेट करें
5. sum = Σ(X XOR A[i]) की गणना करें
6. X और sum वापस करें

पायथन कार्यान्वयन

from math import log2

def search_res(arr, n):
    element = max(arr)
    p = int(log2(element)) + 1
    X = 0
    for i in range(p):
        cnt = sum(1 for x in arr if x & (1 << i))
        if cnt > n // 2:
            X |= (1 << i)
    total = sum(X ^ x for x in arr)
    print(f"X = {X}, Sum = {total}")

arr = [3, 4, 5, 6, 7]
n = len(arr)
search_res(arr, n)

इनपुट

[3, 4, 5, 6, 7]

आउटपुट

X = 7, Sum = 10