मान लीजिए हमारे पास एक सरणी nums है और दो मान l और r हैं। हमें अच्छे जोड़ों (nice pairs) की संख्या ज्ञात करनी है। यहाँ एक अच्छा जोड़ा (i, j) वह है जहां 0 ≤ i < j < nums का आकार और l ≤ (nums[i] XOR nums[j]) ≤ r हो।
उदाहरण के लिए, यदि इनपुट nums = [4,1,7,2], l = 2, r = 6 है, तो आउटपुट 6 होगा क्योंकि अच्छे जोड़े हैं: (1,0): 1 XOR 4 = 5, (1,2): 1 XOR 7 = 6, (1,3): 1 XOR 2 = 3, (0,3): 4 XOR 2 = 6, (0,2): 4 XOR 7 = 3, (2,3): 7 XOR 2 = 5।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
एक फ़ंक्शन test() परिभाषित करें जो nums और x लेता है।
count := nums में तत्वों की आवृत्ति वाला एक मैप।
res := 0
जब तक x शून्येतर है, तब तक:
यदि x विषम है, तो:
res := res + count[a] * count[(x - 1) XOR a] का योग सभी a के लिए count में।
count := कुंजी a/2 और मान (count[a] + count[a XOR 1]) वाला मैप, सभी a के लिए count में।
x = x/2 का भागफल।
res/2 का भागफल लौटाएं।
मुख्य विधि से test(nums, r + 1) - test(nums, l) लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
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
