मान लीजिए हमारे पास संख्याओं की दो सूचियाँ nums1 और nums2 हैं। और दो संख्याएँ lower और upper भी हैं। हमें जोड़े (i, j) की संख्या ढूंढनी है जैसे कि lower <= nums1[i]^2 + nums2[j]^2 <= upper।
इसलिए, यदि इनपुट है nums1 = [5, 3, 2], nums2 = [8, 12, 6], lower = 10, upper = 50, तो आउटपुट होगा 2 क्योंकि जोड़े हैं (1, 2) और (2, 2):
10 <= 3^2 + 6^2 <= 50 = 10 <= 45 <= 5010 <= 2^2 + 6^2 <= 50 = 10 <= 40 <= 50
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
nums1में प्रत्येक तत्व को उसके वर्ग से बदलेंnums2में प्रत्येक तत्व को उसके वर्ग से बदलेंn := nums1का आकारm := nums2का आकार- यदि
n > m, तो:nums1औरnums2को स्वैप करेंnऔरmको स्वैप करें
nums2 :=सूचीnums2को सॉर्ट करेंres := 0nums1में प्रत्येकe1के लिए, करें:st := nums2 में (lower - e1) डालने के लिए सबसे बायां स्थान ताकि तत्व सॉर्ट रहेंen := nums2 में (upper - e1) डालने के लिए सबसे दायां स्थान ताकि तत्व सॉर्ट रहेंcount := en - stres := res + count
resलौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
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)
count = en - st
res += count
return res
nums1 = [5, 3, 2]
nums2 = [8, 12, 6]
lower = 10
upper = 50
print(solve(nums1, nums2, lower, upper))
इनपुट
[5, 3, 2], [8, 12, 6], 10, 50
आउटपुट
2