पायथन में प्रत्येक क्वेरी के लिए अधिकतम XOR खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक सरणी है जिसे आकार n की संख्या कहा जाता है और एक मान b भी है। हम निम्नलिखित क्वेरी को n बार निष्पादित करना चाहते हैं -

• एक गैर-ऋणात्मक मान k <2^m की खोज करें जैसे कि अंकों और k में सभी तत्वों का XOR अधिकतम हो। तो k ith प्रश्न का उत्तर है।

• मौजूदा सरणी अंकों से अंतिम तत्व निकालें।

• हमें एक सरणी उत्तर खोजना है, जहां उत्तर [i] ith प्रश्न का उत्तर है।

इसलिए, यदि इनपुट 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], k =3 क्योंकि 0 XOR 3 =3.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• x :=2^m - 1

• मैं के लिए 0 से लेकर अंकों के आकार -1 तक की सीमा में हूं

  • अंक [i]:=अंक [i] XOR x

  • एक्स:=अंक [i]

• उलटने के बाद वापसी अंक

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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]