1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers LeetCode Solution
In this guide, you will get 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers LeetCode Solution with the best time and space complexity. The solution to Number of Ways Where Square of Number Is Equal to Product of Two Numbers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Ways Where Square of Number Is Equal to Product of Two Numbers
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.
Time Complexity: O(|\texttt{nums1}||\texttt{nums2}|)
Space Complexity: O(|\texttt{nums1}| + |\texttt{nums2}|)
1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers LeetCode Solution in C++
class Solution {
public:
int numTriplets(vector<int>& nums1, vector<int>& nums2) {
return countTriplets(nums1, nums2) + countTriplets(nums2, nums1);
}
private:
// Returns the number of triplet (i, j, k) if A[i]^2 == B[j] * B[k].
int countTriplets(const vector<int>& A, const vector<int>& B) {
int res = 0;
unordered_map<int, int> count;
for (const int b : B)
++count[b];
for (const int a : A) {
const long target = static_cast<long>(a) * a;
for (const auto& [b, freq] : count) {
if (target % b > 0 || !count.contains(target / b))
continue;
if (target / b == b)
res += freq * (freq - 1);
else
res += freq * count[target / b];
}
}
return res / 2;
}
}; /* code provided by PROGIEZ */
1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers LeetCode Solution in Java
class Solution {
public int numTriplets(int[] nums1, int[] nums2) {
return countTriplets(nums1, nums2) + countTriplets(nums2, nums1);
}
// Returns the number of triplet (i, j, k) if A[i]^2 == B[j] * B[k].
private int countTriplets(int[] A, int[] B) {
int res = 0;
Map<Integer, Integer> count = new HashMap<>();
for (final int b : B)
count.merge(b, 1, Integer::sum);
for (final int a : A) {
long target = (long) a * a;
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
final int b = entry.getKey();
final int freq = entry.getValue();
if (target % b > 0 || !count.containsKey((int) (target / b)))
continue;
if (target / b == b)
res += freq * (freq - 1);
else
res += freq * count.get((int) (target / b));
}
}
return res / 2;
}
} // code provided by PROGIEZ
1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers LeetCode Solution in Python
class Solution:
def numTriplets(self, nums1: list[int], nums2: list[int]) -> int:
def countTriplets(A: list[int], B: list[int]):
"""Returns the number of triplet (i, j, k) if A[i]^2 == B[j] * B[k]."""
res = 0
count = collections.Counter(B)
for a in A:
target = a * a
for b, freq in count.items():
if target % b > 0 or target // b not in count:
continue
if target // b == b:
res += freq * (freq - 1)
else:
res += freq * count[target // b]
return res // 2
return countTriplets(nums1, nums2) + countTriplets(nums2, nums1) # code by PROGIEZ
