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