Number of Ways Where Square of Number Is Equal to Product of Two Numbers
MedPrompt
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]where0 <= i < nums1.lengthand0 <= j < k < nums2.length. - Type 2: Triplet (i, j, k) if
nums2[i]2 == nums1[j] * nums1[k]where0 <= i < nums2.lengthand0 <= 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]. (42 = 2 * 8). Example 2:
Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 12 = 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].
Constraints:
1 <= nums1.length, nums2.length <= 10001 <= nums1[i], nums2[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
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 fromarr1equals the product of two numbers fromarr2. The final answer would becount(nums1, nums2) + count(nums2, nums1). - The
countfunction iterates through every elementarr1[i]. For eacharr1[i], it then iterates through all possible pairs(arr2[j], arr2[k])withj < 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
longfor calculations is crucial to prevent integer overflow, as numbers can be up to 10^5, and their square can be up to 10^10.
Walkthrough
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
Time
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
O(1), as we only use a few variables to store counts and intermediate values.
Trade-offs
Pros
Simple to understand and implement.
Cons
Very inefficient and will likely result in a "Time Limit Exceeded" error for the given constraints.
Solutions
Solution
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 walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.