मान लीजिए हमारे पास एक सरणी A है, हमें एक संख्या X ढूंढनी है जैसे कि (A[0] XOR X) + (A[1] XOR X) + ... + A[n-1] XOR X न्यूनतम हो।
यदि इनपुट [3, 4, 5, 6, 7] जैसा है, तो आउटपुट X = 7, Sum = 10 होगा।
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- search_res() नामक एक फंक्शन परिभाषित करें। यह arr, n लेगा:
- element := arr[0]
- i को 0 से arr के आकार तक के लिए, करें:
- यदि arr[i] > element, तो element := arr[i]
- p := log2(element) का पूर्णांक भाग + 1
- X := 0
- i को 0 से p तक के लिए, करें:
- cnt := 0
- j को 0 से n तक के लिए, करें:
- यदि arr[j] & (2^i) शून्येतर है, तो cnt := cnt + 1
- यदि cnt > n/2 का पूर्णांक भाग शून्येतर है, तो X := X + (2^i)
- sum := 0
- i को 0 से n तक के लिए, करें:
- sum := sum + (X XOR arr[i])
- X और sum लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
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
