# 2040. Kth Smallest Product of Two Sorted Arrays
import bisect
from math import ceil
"""
given two sorted 0-indexed integer arrays 'nums1' and 'nums2' as well as an
integer 'k', return the k'th smallest product of 'nums1[i] nums2[i]' where
'0 <= i < nums1.length' and '0 <= j < nums2.length'
"""
class Solution(object):
def kthSmallestProduct(self, nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: int
"""
def check(n):
total = 0
for i in nums1:
if i > 0:
total += bisect.bisect(nums2, n // i)
if i < 0:
total += len(nums2) - bisect.bisect_left(nums2, ceil(n / i))
if i == 0 and n >= 0:
total += len(nums2)
start, end = -(10**10) - 1, 10**10 + 1
while start + 1 < end:
mid = (start + end) // 2
if check(mid) >= k:
end = mid
else:
start = mid
return start + 1
if __name__ == "__main__":
obj = Solution()
print(obj.kthSmallestProduct(nums1=[2, 5], nums2=[3, 4], k=2))
print(obj.kthSmallestProduct(nums1=[-4, -2, 0, 3], nums2=[2, 4], k=6))
print(obj.kthSmallestProduct(nums1=[-2, -1, 0, 1, 2], nums2=[-3, -1, 2, 4, 5], k=3))
