1577. 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
void calc(unordered_map<long, int>& pow, unordered_map<long, int>& other, vector<int>& nums) {
int len(nums.size());
for(int i = 0; i < len; i++) {
pow[1L * nums[i]*nums[i]]++;
for(int j = i + 1; j < len; j++) {
long n = sqrt(1L * nums[i]*nums[j]);
if(n * n == 1L * nums[i]*nums[j])
other[1L * nums[i]*nums[j]]++;
}
}
}
public:
int numTriplets(vector<int>& nums1, vector<int>& nums2) {
unordered_map<long, int> pow1, pow2, other1, other2;
calc(pow1, other1, nums1);
calc(pow2, other2, nums2);
return accumulate(begin(pow1), end(pow1), 0, [&](int res, auto e) {return res + e.second * other2[e.first];}) +
accumulate(begin(pow2), end(pow2), 0, [&](int res, auto e) {return res + e.second * other1[e.first];});
}
};
|
