Number Of Ways Where Square Of Number Is Equal To Product Of Two Numbers - Leetcode Solution

The problem "Number Of Ways Where Square Of Number Is Equal To Product Of Two Numbers" on LeetCode wants us to find the number of pairs (a, b) such that a^2 = b * c, where a, b, and c are all positive integers. We need to return this count as an integer.

The brute force solution of this problem is to iterate over all possible pairs (b, c), and for each pair check if there is any integer a such that a^2 = b * c. However, this approach is too slow and does not work for large numbers.

A better approach is to iterate over all factors of each number b and c, and check if their product equals the square of some number. Let's say we find all factors of b and c, and we obtain the lists of factors Fb and Fc, respectively. Then, for each factor f in Fb and g in Fc, we check if f*g is a perfect square.

To check if a number is a perfect square, we can compute its square root and check if it is an integer. However, computing the square root of a large number is not efficient, so we can use integer division to check if the remainder is zero when dividing the square root by 1.

The pseudocode for this approach is:

1. Initialize a counter to 0
2. Find the factor lists Fb and Fc for b and c, respectively
3. For each f in Fb and g in Fc, do the following: a. Compute the product p = f * g b. If p is a perfect square, increment the counter
4. Return the counter as the answer

Here's the Python implementation of the above approach:

def numTriplets(arr): count = 0 n = len(arr) # Loop over all possible pairs of indices i, j, k for i in range(n): for j in range(i + 1, n): for k in range(j + 1, n): # Check if a^2 = b * c or b^2 = a * c or c^2 = a * b if (arr[i] * arr[i] == arr[j] * arr[k] or arr[j] * arr[j] == arr[i] * arr[k] or arr[k] * arr[k] == arr[i] * arr[j]): count += 1 return count

The time complexity of this solution is O(n^3 log n) in the worst case, where n is the length of the input array. The worst case occurs when all elements of the array are equal and the number of pairs (i, j, k) is in the order of n^3. The log n factor comes from the square root computation. Therefore, this solution may not work efficiently for very large inputs.

There are other, more efficient algorithms for this problem that have a better time complexity. One such approach is based on hashing and has a time complexity of O(n^2). However, it requires additional space for the hash table.

1