1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers

Difficulty: Medium

Related Topics: Hash Table, Math

Given two arrays of integers nums1 and nums2, return the number of triplets formed (type 1 and type 2) under the following rules:

• Type 1: Triplet (i, j, k) if nums1[i]<sup>2</sup>&nbsp;== nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
• Type 2: Triplet (i, j, k) if nums2[i]<sup>2</sup>&nbsp;== nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= j < k < nums1.length.

Example 1:

Input: nums1 = [7,4], nums2 = [5,2,8,9]
Output: 1
Explanation: Type 1: (1,1,2), nums1[1]^2 = nums2[1] * nums2[2]. (4^2 = 2 * 8). 

Example 2:

Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 1^2 = 1 * 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1[i]^2 = nums2[j] * nums2[k].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]^2 = nums1[j] * nums1[k].

Example 3:

Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]
Output: 2
Explanation: There are 2 valid triplets.
Type 1: (3,0,2).  nums1[3]^2 = nums2[0] * nums2[2].
Type 2: (3,0,1).  nums2[3]^2 = nums1[0] * nums1[1].

Example 4:

Input: nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]
Output: 0
Explanation: There are no valid triplets.

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 1 <= nums1[i], nums2[i] <= 10^5

Solution

Language: Python3

class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        rep=0
        rep+=self.getNumTriplets(nums1,nums2)
        rep+=self.getNumTriplets(nums2,nums1)
        return rep
    
    def getNumTriplets(self,nums1,nums2):
        num1=[n**2 for n in nums1]
        num2=[]
        for i in range(len(nums2)-1):
            for j in range(i+1,len(nums2)):
                num2.append(nums2[i]*nums2[j])
        num2.sort()
        num1.sort()
        
        rep=0
        k=0
 &nbsp; &nbsp; &nbsp; &nbsp;while k<len(num1):
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cur=self.exist(num2,num1[k])
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;rep+=cur
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;while k+1<len(num1) and num1[k+1]==num1[k]:
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;rep+=cur
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;k+=1
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;k+=1
 &nbsp; &nbsp; &nbsp; &nbsp;return rep
 &nbsp; &nbsp;
 &nbsp; &nbsp;def exist(self,nums,target):
 &nbsp; &nbsp; &nbsp; &nbsp;l=0
 &nbsp; &nbsp; &nbsp; &nbsp;r=len(nums)-1
 &nbsp; &nbsp; &nbsp; &nbsp;while l<=r:
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;mid=l+(r-l)//2
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if nums[mid]>target:
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;r=mid-1
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;elif nums[mid]<target:
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;l=mid+1
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;else: # nums[mid]==target
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;l=self.leftSearch(nums[:mid+1],target)
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;r=self.rightSearch(nums[mid:],target)+mid
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return r-l+1
 &nbsp; &nbsp; &nbsp; &nbsp;return 0
 &nbsp; &nbsp;
 &nbsp; &nbsp;def leftSearch(self,nums,target):
 &nbsp; &nbsp; &nbsp; &nbsp;l,r=0,len(nums)-1
 &nbsp; &nbsp; &nbsp; &nbsp;while l<=r:
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;mid=l+(r-l)//2
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if nums[mid]==target:
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;r=mid-1
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;else:
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;l=mid+1
 &nbsp; &nbsp; &nbsp; &nbsp;return l
 &nbsp; &nbsp;
 &nbsp; &nbsp;def rightSearch(self,nums,target):
 &nbsp; &nbsp; &nbsp; &nbsp;l,r=0,len(nums)-1
 &nbsp; &nbsp; &nbsp; &nbsp;while l<=r:
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;mid=l+(r-l)//2
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if nums[mid]==target:
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;l=mid+1
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;else:
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;r=mid-1
 &nbsp; &nbsp; &nbsp; &nbsp;return r
 &nbsp; &nbsp; &nbsp; &nbsp;