পাইথনে দুটি লিস্টের বর্গের যোগফল নির্দিষ্ট রেঞ্জে আছে কিনা চেক করা

দুটি লিস্ট nums1, nums2 এবং রেঞ্জ [lower, upper] দেওয়া আছে। জোড়া (i, j) কতটি আছে যাতে lower ≤ nums1[i]² + nums2[j]² ≤ upper।

ইনপুট উদাহরণ

nums1 = [5, 3, 2]
nums2 = [8, 12, 6]
lower = 10, upper = 50

আউটপুট: 2 (জোড়া: (3,6) এবং (2,6))

অ্যালগরিদম

1. দুই লিস্টের সব উপাদান বর্গ করে নিন।
2. ছোট লিস্টটি বাইরলুপে, বড় লিস্ট সর্ট করে বাইনারি সার্চ (bisect_left, bisect_right) দিয়ে বৈধ রেঞ্জ কাউন্ট করুন।

পাইথন কোড

from bisect import bisect_left, bisect_right

def solve(nums1, nums2, lower, upper):
    nums1 = [i * i for i in nums1]
    nums2 = [i * i for i in nums2]
    n, m = len(nums1), len(nums2)
    if n > m:
        nums1, nums2 = nums2, nums1
        n, m = m, n
    nums2 = sorted(nums2)
    res = 0
    for e1 in nums1:
        st = bisect_left(nums2, lower - e1)
        en = bisect_right(nums2, upper - e1)
        res += en - st
    return res

# টেস্ট
print(solve([5,3,2], [8,12,6], 10, 50))  # 2

ব্যাখ্যা

বাইনারি সার্চ ব্যবহার করে O(n log m) টাইমে সমাধান। bisect_left দিয়ে লোয়ার বাউন্ড, bisect_right দিয়ে আপার বাউন্ড।