ধরুন আমাদের একটি অ্যারে সংখ্যা আছে এবং দুটি মান আছে l এবং r, আমাদের চমৎকার জোড়ার সংখ্যা বের করতে হবে। এখানে একটি সুন্দর জোড়া হল একটি জোড়া (i, j) যেখানে 0 <=i
সুতরাং, ইনপুট যদি 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.
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
একটি ফাংশন পরীক্ষা () সংজ্ঞায়িত করুন। এটি সংখ্যা, x
গণনা :=সংখ্যায় উপাদানের ফ্রিকোয়েন্সি সম্বলিত একটি মানচিত্র
res :=0
যখন x অ-শূন্য, কর
যদি x বিজোড় হয়, তাহলে
res :=res + সমস্ত উপাদানের যোগফল (count[a] * count[(x - 1) XOR a) সমস্ত a গণনার জন্য
গণনা :=কী a/2 এবং মান সহ মানচিত্র (গণনা[a] + গণনা[a XOR 1] সমস্ত a গণনার জন্য
x =x/2
res / 2
মূল পদ্ধতি থেকে রিটার্ন পরীক্ষা (সংখ্যা, r + 1) - পরীক্ষা(সংখ্যা, 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
