Square Equals a Pair Product

Medium

You get two arrays of positive integers, first and second. Count index triples of two kinds: - (i, j, k) with first[i]² == second[j] * second[k] and j < k; - (i, j, k) with second[i]² == first[j] * first[k] and j < k. In other words, the square of a number from one array must equal the product of two elements at different positions of the other array. Return the total number of such triples of both kinds.

Example 1

first=[6, 3], second=[4, 9, 12, 1] → 2

6² = 36 = 3 · 12 and 3² = 9 = 9 · 1: two triples with the square taken from first. None work the other way: for instance, 4² = 16, while the only pair product in first is 18.

Example 2

first=[2, 2], second=[2, 2] → 4

Each of the four 2s squared gives 4, which equals the product of the one pair in the other array: 4 triples.

Example 3

first=[5], second=[7] → 0

Each array has a single number, so no pair can be formed.

Constraints

1 ≤ len(first), len(second) ≤ 1000
1 ≤ first[i], second[i] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Math Two Pointers

Similar problems

Roll an Array to the Right Medium Vertical Mirror Line Medium Sorted Parabola Values Medium Equidistant Point Triples Medium One-Way Jump Cycle Medium

Input

first=[6, 3], second=[4, 9, 12, 1]

Expected

Run checks the first 3 tests in your browser. Submit checks all 112 tests on the server, hidden ones included.