পাইথনে অ্যারে থেকে একটি উপাদান নিয়ে সর্বাধিক XOR খুঁজে বের করার প্রোগ্রাম

আমাদের একটি অ্যারে আছে nums যাতে নন-নেগেটিভ মান রয়েছে। আমাদের আরও একটি অ্যারে আছে queries যেখানে queries[i] একটি জোড়া (xi, mi) ধারণ করে। i-তম কোয়ারীর উত্তর হলো xi এবং nums-এর যেকোনো উপাদানের মধ্যকার সর্বাধিক বিটওয়াইজ XOR মান যা mi-এর চেয়ে কম বা সমান। যদি nums-এর সব উপাদান mi-এর চেয়ে বড় হয়, তবে উত্তর -1। তাই আমাদের একটি answer অ্যারে বের করতে হবে যেতে answer-এর আকার queries-এর আকারের সমান এবং answer[i] হলো i-তম কোয়ারীর উত্তর।

উদাহরণস্বরূপ, ইনপুট nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]] হলে আউটপুট হবে [3,3,7], কারণ:

• 0 এবং 1, 1-এর চেয়ে বড় নয়। 0 XOR 3 = 3 এবং 1 XOR 3 = 2, এখানে বড়টি 3।

• 1 XOR 2 = 3।

• 5 XOR 2 = 7।

সমাধানের ধাপসমূহ (বিট ম্যানিপুলেশন + সর্টিং)

• m := nums-এর আকার, n := queries-এর আকার

• queries-কে (i, x, limit) ট্রিপলেটে রূপান্তর করুন প্রতিটি ইন্ডেক্স i এবং জোড়া (x, limit) এর জন্য

• queries-কে limit অনুযায়ী সর্ট করুন

• nums-কে সর্ট করুন

• res := n আকারের অ্যারে ০ দিয়ে ফিল করে

• k = 31 থেকে 0 পর্যন্ত ১ কমানো হারে লুপ চালান:

  • prefixes := একটি নতুন সেট

  • j := 0

  • queries-এর প্রতিটি ইন্ডেক্স i এবং ভ্যালু (x, limit) এর জন্য:

    • j <= m-1 এবং nums[j] <= limit থাকাকালীন:

      • nums[j] >> k-কে prefixes-এ ইনসার্ট করুন

      • j := j + 1

    • যদি prefixes খালি হয়, তবে:

      • res[i] := -1

    • অন্যথায়:

      • res[i] <<= 1

      • target := res[i] ^ 1

      • যদি (x >> k) ^ target prefixes-এ থাকে, তবে:

        • res[i] := target

• res রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

def solve(nums, queries):
    m, n = len(nums), len(queries)
    queries = sorted(((i, x, limit) for i, (x, limit) in enumerate(queries)), key=lambda x: x[2])
    nums = sorted(nums)
    res = [0] * n
    for k in range(31, -1, -1):
        prefixes = set()
        j = 0
        for i, x, limit in queries:
            while j <= m - 1 and nums[j] <= limit:
                prefixes.add(nums[j] >> k)
                j += 1
            if not prefixes:
                res[i] = -1
            else:
                res[i] <<= 1
                target = res[i] ^ 1
                if (x >> k) ^ target in prefixes:
                    res[i] = target
    return res

nums = [0,1,2,3,4]
queries = [[3,1],[1,3],[5,6]]
print(solve(nums, queries))

ইনপুট

[0,1,2,3,4], [[3,1],[1,3],[5,6]]

আউটপুট

[3, 3, 7]