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

MEDIUM

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

Example 2:

Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 1² = 1 * 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1[i]² = nums2[j] * nums2[k].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]² = 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]² = nums2[0] * nums2[2].
Type 2: (3,0,1).  nums2[3]² = nums1[0] * nums1[1].

Constraints:

1 <= nums1.length, nums2.length <= 1000
1 <= nums1[i], nums2[i] <= 10⁵

Approaches

Checkout 3 different approaches to solve Number of Ways Where Square of Number Is Equal to Product of Two Numbers. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach involves iterating through all possible triplets (i, j, k) for both Type 1 and Type 2, checking if the condition num^2 = product holds for each triplet. This is the most straightforward but also the slowest method.

Algorithm

The problem can be broken down into two symmetric subproblems: counting Type 1 triplets and counting Type 2 triplets. The total count is the sum of these two.
We can create a helper function, say count(arr1, arr2), which counts triplets where a square of a number from arr1 equals the product of two numbers from arr2. The final answer would be count(nums1, nums2) + count(nums2, nums1).
The count function iterates through every element arr1[i]. For each arr1[i], it then iterates through all possible pairs (arr2[j], arr2[k]) with j < k.
Inside the innermost loop, it checks if (long)arr1[i] * arr1[i] == (long)arr2[j] * arr2[k]. If the condition is true, a counter is incremented.
Using long for calculations is crucial to prevent integer overflow, as numbers can be up to 10^5, and their square can be up to 10^10.

The core idea is to check every single combination of indices (i, j, k) that satisfy the problem's constraints. We can implement a helper function that takes two arrays, arr1 and arr2, and counts the number of triplets where the square of an element from arr1 equals the product of two distinct elements from arr2. By calling this helper function twice with the arguments swapped (count(nums1, nums2) and count(nums2, nums1)), we can find the total number of valid triplets.

class Solution {
    public int numTriplets(int[] nums1, int[] nums2) {
        return countTriplets(nums1, nums2) + countTriplets(nums2, nums1);
    }

    private int countTriplets(int[] arr1, int[] arr2) {
        int count = 0;
        int n = arr1.length;
        int m = arr2.length;
        if (m < 2) {
            return 0;
        }
        for (int i = 0; i < n; i++) {
            long square = (long) arr1[i] * arr1[i];
            for (int j = 0; j < m; j++) {
                for (int k = j + 1; k < m; k++) {
                    if (square == (long) arr2[j] * arr2[k]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(N * M^2 + M * N^2), where N is the length of `nums1` and M is the length of `nums2`. The helper function `count(arr1, arr2)` takes `O(N * M^2)`. The total time is the sum for both types of triplets. This is too slow for the given constraints.Space Complexity: O(1), as we only use a few variables to store counts and intermediate values.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Very inefficient and will likely result in a "Time Limit Exceeded" error for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Number of Ways Where Square of Number Is Equal to Product of Two Numbers. Click on different languages to view the code.

class Solution {
public
  int numTriplets(int[] nums1, int[] nums2) {
    Map<Integer, Integer> cnt1 = new HashMap<>();
    Map<Integer, Integer> cnt2 = new HashMap<>();
    for (int v : nums1) {
      cnt1.put(v, cnt1.getOrDefault(v, 0) + 1);
    }
    for (int v : nums2) {
      cnt2.put(v, cnt2.getOrDefault(v, 0) + 1);
    }
    long ans = 0;
    for (var e1 : cnt1.entrySet()) {
      long a = e1.getKey(), x = e1.getValue();
      for (var e2 : cnt2.entrySet()) {
        long b = e2.getKey(), y = e2.getValue();
        if ((a * a) % b == 0) {
          long c = a * a / b;
          if (b == c) {
            ans += x * y * (y - 1);
          } else {
            ans += x * y * cnt2.getOrDefault((int)c, 0);
          }
        }
        if ((b * b) % a == 0) {
          long c = b * b / a;
          if (a == c) {
            ans += x * (x - 1) * y;
          } else {
            ans += x * y * cnt1.getOrDefault((int)c, 0);
          }
        }
      }
    }
    return (int)(ans >> 1);
  }
}

Video Solution

Watch the video walkthrough for Number of Ways Where Square of Number Is Equal to Product of Two Numbers

Patterns:

MathTwo Pointers

Data Structures:

ArrayHash Table