Number of Ways Where Square of Number Is Equal to Product of Two Numbers
Number of Ways Where Square of Number Is Equal to Product of Two Numbers solution: step-by-step approach, complexity and code in Python, Java, C++ and…
Number of Ways Where Square of Number Is Equal to Product of Two Numbers is a medium coding problem on arrays, hash table and math, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Math, Two Pointers
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two arrays of positive integers, nums1 and nums2. Count the triplets of these two types:
- Type 1:
(i, j, k)withnums1[i]^2 == nums2[j] * nums2[k], where0 <= i < nums1.lengthand0 <= j < k < nums2.length. - Type 2:
(i, j, k)withnums2[i]^2 == nums1[j] * nums1[k], where0 <= i < nums2.lengthand0 <= j < k < nums1.length.
Return the total number of triplets of both types.
Example 1
Input: nums1 = [4,6], nums2 = [2,8,3,12,1]
Output: 2
Explanation: Type 1: 4² = 16 = 2 · 8 and 6² = 36 = 3 · 12. No square of `nums2` is the product of 4 and 6.
Example 2
Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: Type 1: 2 choices of `i` times 3 pairs `(j, k)` = 6. Type 2: 3 choices of `i` times 1 pair = 3.
Example 3
Input: nums1 = [3], nums2 = [5]
Output: 0
Explanation: Neither array has two elements to multiply.
Constraints
1 <= nums1.length, nums2.length <= 10001 <= nums1[i], nums2[i] <= 10^5
Hints for Number of Ways Where Square of Number Is Equal to Product of Two Numbers
Hint 1
The two types are the same question with the arrays swapped — solve one direction and call it twice.
Hint 2
For a fixed square
s = x², you need the number of index pairsj < kin the other array with products: a two-sum on products.Hint 3
Count the other array's values in a hash map. For each distinct value
vwithv² < sdividings, addcount[v] · count[s / v]; ifv² == s, addcount[v] · (count[v] - 1) / 2.
How to solve Number of Ways Where Square of Number Is Equal to Product of Two Numbers
Each type is a "two-product" count: for every square s from one array, count unordered pairs in the other array multiplying to s. A frequency map of the other array answers that by walking its distinct values v and looking up the partner s / v.
Approach
- Write
count(xs, ys): build a frequency map ofys. - For each
xinxs, lets = x · x(64-bit). For every distinctvin the map: ifv · v < sands % v == 0, addfreq[v] · freq[s / v]; ifv · v == s, addfreq[v] · (freq[v] - 1) / 2. - Return
count(nums1, nums2) + count(nums2, nums1).
Why it works
Restricting to v < s / v visits each unordered pair of distinct values once, and the product of their frequencies counts every index pair with those values. Pairs of equal values (v = s / v) are chosen within one bucket, C(freq, 2) ways. Every index pair j < k with ys[j] · ys[k] = s falls in exactly one of these cases.
Complexity
- Time —
O(n · d1 + m · d2) with d the distinct counts - Space —
O(n + m)
Pitfalls
x²reaches 10^10 — keep it, and every product, in 64 bits.- Counting ordered pairs (both
(v, w)and(w, v)) doubles the answer. - Equal values need
C(c, 2)pairs, notc².
Reference solution
Python
from typing import List
from collections import Counter
def numTriplets(nums1: List[int], nums2: List[int]) -> int:
def count(xs, ys):
freq = Counter(ys)
total = 0
for x in xs:
s = x * x
for v, c in freq.items():
if v * v == s:
total += c * (c - 1) // 2
elif v * v < s and s % v == 0:
total += c * freq.get(s // v, 0)
return total
return count(nums1, nums2) + count(nums2, nums1)Java
public static int numTriplets(int[] nums1, int[] nums2) {
return (int) (countWays(nums1, nums2) + countWays(nums2, nums1));
}
private static long countWays(int[] xs, int[] ys) {
Map<Long, Long> freq = new HashMap<>();
for (int y : ys) freq.merge((long) y, 1L, Long::sum);
long total = 0;
for (int x : xs) {
long s = (long) x * x;
for (Map.Entry<Long, Long> e : freq.entrySet()) {
long v = e.getKey(), c = e.getValue();
if (v * v == s) total += c * (c - 1) / 2;
else if (v * v < s && s % v == 0) total += c * freq.getOrDefault(s / v, 0L);
}
}
return total;
}C++
static long long countWays(const vector<int>& xs, const vector<int>& ys) {
unordered_map<long long, long long> freq;
for (int y : ys) freq[y]++;
long long total = 0;
for (int x : xs) {
long long s = (long long)x * x;
for (auto& e : freq) {
long long v = e.first, c = e.second;
if (v * v == s) total += c * (c - 1) / 2;
else if (v * v < s && s % v == 0) {
auto it = freq.find(s / v);
if (it != freq.end()) total += c * it->second;
}
}
}
return total;
}
int numTriplets(vector<int>& nums1, vector<int>& nums2) {
return (int)(countWays(nums1, nums2) + countWays(nums2, nums1));
}JavaScript
var numTriplets = function(nums1, nums2) {
var count = function(xs, ys) {
var freq = new Map();
for (var i = 0; i < ys.length; i++) freq.set(ys[i], (freq.get(ys[i]) || 0) + 1);
var keys = Array.from(freq.keys());
var total = 0;
for (var a = 0; a < xs.length; a++) {
var s = xs[a] * xs[a]; // at most 10^10: exact in a double
for (var b = 0; b < keys.length; b++) {
var v = keys[b], c = freq.get(v);
if (v * v === s) total += c * (c - 1) / 2;
else if (v * v < s && s % v === 0) total += c * (freq.get(s / v) || 0);
}
}
return total;
};
return count(nums1, nums2) + count(nums2, nums1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets