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

Medium
1788.

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 is a medium coding problem on arrays, hash table and math, asked in Google interviews.

You are given two arrays of positive integers, nums1 and nums2. Count the triplets of these two types:

  • Type 1: (i, j, k) with nums1[i]^2 == nums2[j] * nums2[k], where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
  • Type 2: (i, j, k) with nums2[i]^2 == nums1[j] * nums1[k], where 0 <= i < nums2.length and 0 <= 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 <= 1000
  • 1 <= nums1[i], nums2[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var numTriplets = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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) with nums1[i]^2 == nums2[j] * nums2[k], where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
  • Type 2: (i, j, k) with nums2[i]^2 == nums1[j] * nums1[k], where 0 <= i < nums2.length and 0 <= 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 <= 1000
  • 1 <= nums1[i], nums2[i] <= 10^5

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

  1. Hint 1

    The two types are the same question with the arrays swapped — solve one direction and call it twice.

  2. Hint 2

    For a fixed square s = x², you need the number of index pairs j < k in the other array with product s: a two-sum on products.

  3. Hint 3

    Count the other array's values in a hash map. For each distinct value v with v² < s dividing s, add count[v] · count[s / v]; if v² == s, add count[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

  1. Write count(xs, ys): build a frequency map of ys.
  2. For each x in xs, let s = x · x (64-bit). For every distinct v in the map: if v · v < s and s % v == 0, add freq[v] · freq[s / v]; if v · v == s, add freq[v] · (freq[v] - 1) / 2.
  3. 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, not c².

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