ধরুন আমাদের একটি অ্যারে সংখ্যা আছে এবং দুটি মান আছে 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