মনে করুন আমাদের একটি সংখ্যার তালিকা nums এবং একটি কোয়েরির তালিকা আছে যেখানে প্রতিটি কোয়েরিতে [x, limit] থাকে। আমাদের একটি তালিকা খুঁজে বের করতে হবে যাতে প্রতিটি কোয়েরি [x, limit]-এর জন্য, আমরা nums-এ একটি উপাদান e খুঁজে পাই যাতে e ≤ limit এবং e XOR x সর্বোচ্চ হয়। যদি এমন কোনো উপাদান না থাকে, তবে -1 রিটার্ন করুন।
উদাহরণস্বরূপ, যদি ইনপুট হয় nums = [3, 5, 9], queries = [[4, 6],[2, 0]], তবে আউটপুট হবে [3, -1], কারণ প্রথম কোয়েরির জন্য, আমরা nums-এ 2 বা 4 ব্যবহার করতে পারি। 3 ^ 4 = 7, 5 ^ 4 = 3, তাই আমরা 3 নির্বাচন করি যা বড় XOR দেয়। দ্বিতীয় কোয়েরির জন্য, 0-এর চেয়ে ছোট বা সমান এমন কোনো সংখ্যা নেই, তাই আমরা এটিকে -1 সেট করি।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
trie := একটি নতুন ম্যাপ
একটি bits() ফাংশন সংজ্ঞায়িত করুন। এটি i নিবে
i-এর 32-বিট বাইনারি রিপ্রেজেন্টেশন রিটার্ন করুন
একটি insert ফাংশন সংজ্ঞায়িত করুন। এটি i নিবে
node := trie
bits(i)-এ প্রতিটি c-এর জন্য, করুন
node := যদি c node-এ না থাকে, তবে তার ভিতরে একটি খালি ম্যাপ যোগ করুন
node[2] := i
একটি query() ফাংশন সংজ্ঞায়িত করুন। এটি i নিবে
node := trie
bits(i)-এ প্রতিটি c-এর জন্য, করুন
rc := c XOR 1
node := node[rc] যদি থাকে অন্যথায় node[c]
node[2] রিটার্ন করুন
মূল মেথড থেকে নিচের কাজগুলো করুন
A তালিকা সাজান
B := প্রতিটি কোয়েরি সূচক i এবং কোয়েরি মান x এবং limit-এর জন্য (i, x, limit) আকারের উপাদানগুলির একটি তালিকা। তারপর limit অনুযায়ী সাজান
(j, n, ans) := (0, A-এর আকার, কোয়েরির আকারের একটি তালিকা, -1 দিয়ে ভরা)
B-এ প্রতিটি সূচক i এবং মান x এবং limit-এর জন্য, করুন
যখন j < n এবং A[j] ≤ limit, করুন
insert(A[j])
j := j + 1
যদি j নন-জিরো হয়, তবে
ans[i] := query(x)
ans রিটার্ন করুন
উদাহরণ (পাইথন)
বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:
class Solution: def solve(self, A, queries): trie = {} def bits(i): return map(int, bin(i)[2:].zfill(32)) def insert(i): node = trie for c in bits(i): node = node.setdefault(c, {}) node[2] = i def query(i): node = trie for c in bits(i): rc = c ^ 1 node = node.get(rc, node.get(c)) return node[2] A.sort() B = sorted([(i, x, limit) for i, (x, limit) in enumerate(queries)], key=lambda x: x[2]) j, n, ans = 0, len(A), [-1] * len(queries) for i, x, limit in B: while j < n and A[j] <= limit: insert(A[j]) j += 1 if j: ans[i] = query(x) return ans ob = Solution() nums = [3, 5, 9] queries = [ [4, 6], [2, 0] ] print(ob.solve(nums, queries))ইনপুট
[3, 5, 9], [[4, 6],[2, 0]]
আউটপুট
[3, -1]
