मान लीजिए कि हमारे पास एक सरणी संख्या है और दो मान l और r हैं, हमें अच्छे जोड़े की संख्या ज्ञात करनी है। यहाँ एक अच्छी जोड़ी एक जोड़ी है (i, j) जहाँ 0 <=i
इसलिए, यदि इनपुट अंकों की तरह है =[4,1,7,2] l =2 r =6, तो आउटपुट 6 होगा क्योंकि अच्छे जोड़े हैं (10):1 एक्सओआर 4 =5, (1) ,2):1 एक्सओआर 7 =6, (1,3):1 एक्सओआर 2 =3, (0,3):4 एक्सओआर 2 =6, (0,2):4 एक्सओआर 7 =3, (2,3 ):7 एक्सओआर 2 =5.
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
फ़ंक्शन टेस्ट() को परिभाषित करें। इसमें अंक लगेंगे, x
गिनती :=एक नक्शा जिसमें अंकों में तत्वों की आवृत्ति होती है
रेस :=0
जबकि x शून्य नहीं है, करें
अगर x विषम है, तो
रेस:=रेस + के सभी तत्वों का योग (गिनती [ए] * गिनती [(एक्स - 1) एक्सओआर ए) सभी के लिए गिनती में
गिनती :=कुंजी a/2 और मान के साथ नक्शा (गिनती [a] + गिनती [a XOR 1] सभी के लिए गिनती में
x =x/2 का भागफल
रेस / 2 का रिटर्न भागफल
मुख्य विधि से वापसी परीक्षण(अंक, आर + 1) - परीक्षण(अंक, एल)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें
उदाहरण
from collections import Counter
def solve(nums, l, r):
def test(nums, x):
count = Counter(nums)
res = 0
while x:
if x & 1:
res += sum(count[a] * count[(x - 1) ^ a] for a in count)
count = Counter({a >> 1: count[a] + count[a ^ 1] for a in count})
x >>= 1
return res // 2
return test(nums, r + 1) - test(nums, l)
nums = [4,1,7,2]
l = 2
r = 6
print(solve(nums, l, r)) इनपुट
[4,1,7,2], 2, 6
आउटपुट
6
