We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

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

Difficulty: Medium

Problem Description

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]^2 == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
  • Type 2: Triplet (i, j, k) if nums2[i]^2 == nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= j < k < nums1.length.

Key Insights

  • The problem requires checking combinations of elements from two arrays to find valid triplets that satisfy specific mathematical conditions.
  • Efficiently counting pairs in one array that can form the required product with squares from the other array is crucial.
  • The use of hash maps can help keep track of the frequency of potential products to speed up the search for valid triplets.

Space and Time Complexity

Time Complexity: O(n^2 + m^2) where n is the length of nums1 and m is the length of nums2. This accounts for the nested loops to calculate potential products and squares. Space Complexity: O(m + n) for storing the count of products and squares in hash maps.

Solution

The solution involves iterating through each element of nums1 to calculate its square and checking for pairs in nums2 whose product equals this square. Similarly, it calculates the square of each element in nums2 and checks for pairs in nums1. Hash maps are used to efficiently count how many pairs can form the required products.

Code Solutions

def numTriplets(nums1, nums2):
    from collections import Counter

    def countPairs(nums, target):
        count = 0
        freq = Counter(nums)
        for num in nums:
            complement = target // num
            if target % num == 0:
                count += freq[complement]
                if complement == num:
                    count -= 1  # avoid counting the same pair
        return count // 2  # each pair is counted twice

    total_triplets = 0
    # Type 1 triplets
    squares1 = [x * x for x in nums1]
    products2 = [nums2[j] * nums2[k] for j in range(len(nums2)) for k in range(j + 1, len(nums2))]
    total_triplets += sum(countPairs(products2, sq) for sq in squares1)

    # Type 2 triplets
    squares2 = [x * x for x in nums2]
    products1 = [nums1[j] * nums1[k] for j in range(len(nums1)) for k in range(j + 1, len(nums1))]
    total_triplets += sum(countPairs(products1, sq) for sq in squares2)

    return total_triplets
← Back to All Questions