# 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers

## Problem Description

The problem requires us to calculate the number of special triplets between two different arrays. We have two types of triplets:

• Type 1 triplet is formed when we select one number from `nums1` and two numbers from `nums2`. The condition to form this triplet is when the square of the selected number from `nums1` is equivalent to the product of the two selected numbers from `nums2`.

• Type 2 triplet is the reverse of Type 1: we select one number from `nums2` and two numbers from `nums1`, and the square of the number from `nums2` should be equivalent to the product of the two numbers from `nums1`.

For both types, we need to pay attention to the distinct indices of `j` and `k` (i.e., `j < k`) when selecting from the same array.

## Intuition

To arrive at the solution, we need to compare each number's square from one array to all possible products of pairs from the other array. Instead of direct pairwise comparisons, we use a more efficient approach by leveraging hashmap (dictionary in Python) to store the frequency of each number in both arrays.

• We use the `Counter` class from the `collections` module for efficiently counting the occurrences of elements in `nums1` and `nums2`, thereby avoiding repeated computations that would result from iterating through the same values multiple times.

• We iterate over every unique number in one array, and for each number, we check whether its square can be formed by the product of two numbers in the other array.

• To manage occurrences and ordering (to assure `j < k`), we apply a combination logic: if a squared number is divisible by a number in the other array, then there must be a corresponding pair that can produce that square when multiplied together.

• We handle the special case where the two numbers from the same array are the same by making sure we calculate the combination correctly (e.g., if we have two 2's in `nums2` and one 4 in `nums1`, the count should be incremented by `1 * 2 * (2-1)` for Type 1).

• Since each triplet will be counted twice (once for each order of `j` and `k`), we divide the result by two before returning the final answer.

By using hashmaps for counting and then iterating through each number in `nums1` and `nums2`, we can compute the total number of triplets in an efficient way, avoiding the brute-force method which would be too slow for large arrays.

## Solution Approach

The solution's approach can be understood step by step as follows:

1. Count Frequencies: We begin by counting the frequencies of each number in `nums1` and `nums2`. This is done using the `Counter` class from the `collections` module in Python. The `Counter` class creates a hashmap where the key is the number from the array and the value is the count of occurrences of that number.

2. Initialization: The code then initializes an `ans` variable to accumulate the count of the triplets.

3. Iterating through the arrays:

• For each unique number`a` in `cnt1` (the Counter object for `nums1`), we check if `a^2` is divisible by any number `b` in `cnt2` (the Counter object for `nums2`).

• If `a^2` is divisible by `b`, we find `c = a^2 // b`, which would be the complementary number needed for the product `b * c` to equal `a^2`.
• We then update `ans` according to the count of `b` and `c` in `cnt2`, taking care to handle the case where `b` and `c` are the same.
• We repeat a similar process iterating through `cnt2` and checking divisibility with respect to each number in `cnt1`, looking for complementary pairs in `cnt1`.

4. Combination Logic:

• When we find a valid division, i.e., where `a^2 % b == 0`, we consider two cases:
• If `b` and `c` are the same, we've found a case where the same number is used twice to contribute to the triplet count. We account for this by calculating `x * y * (y - 1)` (or `x * (x - 1) * y`), where `x` and `y` are the counts of `a` and `b` or `b` and `a` respectively. This accounts for choosing two out of `y` elements (the `(y - 1)` part).
• If `b` and `c` are different, we don't have to account for ordering, so we simply multiply the occurrence counts: `x * y * cnt2[c]` (or `x * y * cnt1[c]`).
5. Double Counting Adjustment:

• Since each triplet has been counted twice due to the two possible positions of `j` and `k`, we divide the total count by 2. This is performed by the `ans >> 1` statement, which is a bit-shift to the right by one position, effectively halving the number.

By leveraging the efficient look-up times of hashmaps to track frequencies and by using mathematical divisibility to identify valid triplet conditions, the algorithm avoids the need to perform a brute-force search through all possible triplet combinations. This results in a much faster solution that can handle larger input arrays.

๐ช
Level Up Your
Algo Skills

### Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Suppose we have the following two arrays:

• `nums1 = [2, 3]`
• `nums2 = [1, 2, 6]`

#### Step 1: Count Frequencies

Firstly, we count the occurrences of each number in both arrays.

• For `nums1`, the frequency would be: `{2: 1, 3: 1}`
• For `nums2`, the frequency would be: `{1: 1, 2: 1, 6: 1}`

#### Step 2: Initialization

We initialize an accumulator for the results named `ans` with an initial value of `0`.

#### Step 3: Iterating through the arrays

Now we iterate through the array `nums1`:

• For `a = 2` from `nums1`, its square is `2^2 = 4`. Now we check if 4 can be formed by multiplying any two numbers in `nums2`.

• We find that `b = 2` from `nums2` is a factor of `4`. The complementary number needed is `c = 4 // 2 = 2`, which is also present in `nums2`.
• Since `b` and `c` are the same, we use the combination logic for the count: `1 (count of `a`) * 1 (count of `b`) * (1 - 1) (because we're selecting 2 from a count of 1)`, which results in 0, so no triplet is formed for `a = 2`.
• For `a = 3` from `nums1`, we get `3^2 = 9`. No pairs in `nums2` multiply to 9, so there are no triplets for `a = 3`.

Now iterate through `nums2`:

• For `b = 1` from `nums2`, `b^2 = 1`. No pair in `nums1` will multiply to 1, so no triplets are formed.

• For `b = 2` from `nums2`, `b^2 = 4`. There is a number `2` in `nums1` which when squared gives 4, thus forming a triplet (2 from `nums2`, 2 and 2 from `nums1`). In this case, `ans` is updated by `1 (count of `b`in`nums2`) * 1 * (1 - 1)` which results in 0 and does not change `ans`.

• For `b = 6` from `nums2`, `b^2 = 36`. There are no pairs in `nums1` that can multiply to give 36, so no triplets are formed.

#### Step 4: Combination Logic

During our iterations, we encountered both scenarios:

• Same number from `nums2` used twice (e.g., 2 * 2 for `nums1` when `a = 2`).
• Attempts to form a valid product with different `b` and `c` from `nums2` or `nums1` which did not result in any valid triplets.

#### Step 5: Double Counting Adjustment

In our example, we would then divide the final accumulated count by 2 to correct for double counting. However, as we have not found any valid triplets, `ans` will remain at `0`.

Therefore, given this small example, the number of special triplets we can form is zero.

## Python Solution

``````1from collections import Counter
2
3class Solution:
4    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
5        # Create counters for both arrays
6        counter_nums1 = Counter(nums1)
7        counter_nums2 = Counter(nums2)
8
9        # Initialize the answer to 0
10        answer = 0
11
12        # Loop through each unique number in the first list
13        for num1, count1 in counter_nums1.items():
14            # Loop through each unique number in the second list
15            for num2, count2 in counter_nums2.items():
16                # Check if the square of the number from the first list is divisible by the number from the second list
17                if num1 * num1 % num2 == 0:
18                    # Find the corresponding pair number that can be multiplied by num2 to get num1 squared
19                    pair_num = num1 * num1 // num2
20                    # If the number in the second list is the same as the pair number
21                    if num2 == pair_num:
22                        # Increment the answer with the combination count (n * (n-1)) for duplicates
23                        answer += count1 * count2 * (count2 - 1)
24                    else:
25                        # Otherwise increment the answer with the product of the counts
26                        answer += count1 * count2 * counter_nums2[pair_num]
27
28                # Check if the square of the number from the second list is divisible by the number from the first list
29                if num2 * num2 % num1 == 0:
30                    # Find the corresponding pair number that can be multiplied by num1 to get num2 squared
31                    pair_num = num2 * num2 // num1
32                    # If the number in the first list is the same as the pair number
33                    if num1 == pair_num:
34                        # Increment the answer with the combination count (n * (n-1)) for duplicates
35                        answer += count1 * (count1 - 1) * count2
36                    else:
37                        # Otherwise increment the answer with the product of the counts
38                        answer += count1 * count2 * counter_nums1[pair_num]
39
40        # We counted each triplet twice, so divide the answer by 2
41        return answer >> 1  # Shifting right by 1 is equivalent to dividing by 2
42``````

## Java Solution

``````1class Solution {
2    public int numTriplets(int[] nums1, int[] nums2) {
3        // Maps to store the frequency count of each number in nums1 and nums2
4        Map<Integer, Integer> frequencyCount1 = new HashMap<>();
5        Map<Integer, Integer> frequencyCount2 = new HashMap<>();
6
7        // Populate the frequency maps for nums1 and nums2
8        for (int value : nums1) {
9            frequencyCount1.put(value, frequencyCount1.getOrDefault(value, 0) + 1);
10        }
11        for (int value : nums2) {
12            frequencyCount2.put(value, frequencyCount2.getOrDefault(value, 0) + 1);
13        }
14
15        long answer = 0; // Initialize counter for the number of triplets
16
17        // Iterate through each entry in the first frequency count map
18        for (var entry1 : frequencyCount1.entrySet()) {
19            long number1 = entry1.getKey(), count1 = entry1.getValue();
20            // Iterate through each entry in the second frequency count map
21            for (var entry2 : frequencyCount2.entrySet()) {
22                long number2 = entry2.getKey(), count2 = entry2.getValue();
23
24                // Check if the square of number1 is divisible by number2
25                if ((number1 * number1) % number2 == 0) {
26                    long number3 = number1 * number1 / number2;
27                    if (number2 == number3) {
28                        // If number2 and number3 are the same, update the answer accordingly
29                        answer += count1 * count2 * (count2 - 1);
30                    } else {
31                        // Otherwise, calculate the triplet count for different number2 and number3
32                        answer += count1 * count2 * frequencyCount2.getOrDefault((int) number3, 0);
33                    }
34                }
35                // Check if the square of number2 is divisible by number1
36                if ((number2 * number2) % number1 == 0) {
37                    long number3 = number2 * number2 / number1;
38                    if (number1 == number3) {
39                        // If number1 and number3 are the same, update the answer accordingly
40                        answer += count1 * (count1 - 1) * count2;
41                    } else {
42                        // Otherwise, calculate the triplet count for different number1 and number3
43                        answer += count1 * count2 * frequencyCount1.getOrDefault((int) number3, 0);
44                    }
45                }
46            }
47        }
48
49        // Each triplet is counted twice, so divide by 2 to get the correct count
50        return (int) (answer >> 1);
51    }
52}
53``````

## C++ Solution

``````1#include <unordered_map>
2#include <vector>
3
4class Solution {
5public:
6    int numTriplets(std::vector<int>& nums1, std::vector<int>& nums2) {
7        // Unordered maps to store the frequency count of each number in nums1 and nums2
8        std::unordered_map<int, int> frequencyCount1;
9        std::unordered_map<int, int> frequencyCount2;
10
11        // Populate the frequency maps for nums1 and nums2
12        for (int value : nums1) {
13            frequencyCount1[value]++;
14        }
15        for (int value : nums2) {
16            frequencyCount2[value]++;
17        }
18
19        long answer = 0; // Initialize counter for the number of triplets
20
21        // Iterate through each entry in the first frequency count map
22        for (auto& entry1 : frequencyCount1) {
23            long number1 = entry1.first;
24            long count1 = entry1.second;
25            // Iterate through each entry in the second frequency count map
26            for (auto& entry2 : frequencyCount2) {
27                long number2 = entry2.first;
28                long count2 = entry2.second;
29
30                // Check if the square of number1 is divisible by number2
31                if ((number1 * number1) % number2 == 0) {
32                    long number3 = (number1 * number1) / number2;
33                    if (number2 == number3) {
34                        // If number2 and number3 are the same, update the answer accordingly
35                        answer += count1 * count2 * (count2 - 1);
36                    } else {
37                        // Otherwise, calculate the triplet count for different number2 and number3
38                        answer += count1 * count2 * frequencyCount2[(int) number3];
39                    }
40                }
41                // Check if the square of number2 is divisible by number1
42                if ((number2 * number2) % number1 == 0) {
43                    long number3 = (number2 * number2) / number1;
44                    if (number1 == number3) {
45                        // If number1 and number3 are the same, update the answer accordingly
46                        answer += count1 * (count1 - 1) * count2;
47                    } else {
48                        // Otherwise, calculate the triplet count for different number1 and number3
49                        answer += count1 * count2 * frequencyCount1[(int) number3];
50                    }
51                }
52            }
53        }
54
55        // Each triplet is counted twice, so divide by 2 to get the correct count
56        return (int) (answer / 2);
57    }
58};
59``````

## Typescript Solution

``````1let frequencyCount1: Map<number, number> = new Map();
2let frequencyCount2: Map<number, number> = new Map();
3
4function populateFrequencyMap(nums: number[], frequencyMap: Map<number, number>): void {
5  // Populate the frequency map with numbers from the given array
6  nums.forEach(value => {
7    frequencyMap.set(value, (frequencyMap.get(value) || 0) + 1);
8  });
9}
10
11function numTriplets(nums1: number[], nums2: number[]): number {
12  // Initializing the frequency maps for nums1 and nums2
13  populateFrequencyMap(nums1, frequencyCount1);
14  populateFrequencyMap(nums2, frequencyCount2);
15
16  let answer: number = 0; // Initialize counter for the number of triplets
17
18  // Iterate through each key-value pair in frequencyCount1
19  frequencyCount1.forEach((count1, number1) => {
20    // Iterate through each key-value pair in frequencyCount2
21    frequencyCount2.forEach((count2, number2) => {
22      let product1: number = number1 * number1;
23      let product2: number = number2 * number2;
24
25      // Check if product1 is divisible by number2
26      if (product1 % number2 === 0) {
27        let number3: number = product1 / number2;
28        if (number2 === number3) {
29          // Update the answer if both numbers are the same
30          answer += count1 * count2 * (count2 - 1);
31        } else {
32          // Calculate the triplet count for different number2 and number3
33          answer += count1 * count2 * (frequencyCount2.get(number3) || 0);
34        }
35      }
36
37      // Check if product2 is divisible by number1
38      if (product2 % number1 === 0) {
39        let number3: number = product2 / number1;
40        if (number1 === number3) {
41          // Update the answer if both numbers are the same
42          answer += count1 * (count1 - 1) * count2;
43        } else {
44          // Calculate the triplet count for different number1 and number3
45          answer += count1 * count2 * (frequencyCount1.get(number3) || 0);
46        }
47      }
48    });
49  });
50
51  // Each triplet is counted twice, so divide by 2 to get the correct count
52  return answer / 2;
53}
54``````

## Time and Space Complexity

### Time Complexity

The time complexity of the code is determined by the nested loops over two counters (`cnt1` and `cnt2`) which are created from `nums1` and `nums2`. Each `Counter` object will have at most `n` elements, where `n` is the length of the corresponding input list.

There is a nested for-loop structure where we iterate over all combinations of elements from `cnt1` and `cnt2`. Therefore, in the worst case, the number of iterations is proportional to the product of the sizes of `cnt1` and `cnt2`. If `n1` is the number of unique elements in `nums1` and `n2` is the number of unique elements in `nums2`, the time complexity can be approximated by `O(n1 * n2)`.

However, for each pair of `(a, b)` there are a couple of `if` conditions and lookups in the corresponding counter dictionaries, which operate in constant time on average due to the hash table implementation of Python dictionaries. Hence, these operations do not significantly affect the overall time complexity in terms of Big-O notation.

Taking the above into consideration, the overall time complexity is `O(n1 * n2)`.

### Space Complexity

Space complexity is determined by the additional space used by the program excluding the input itself. In this case, we have two `Counter` objects, `cnt1` and `cnt2`. The space complexity will be proportional to the number of unique elements in `nums1` and `nums2`.

Hence, if `n1` and `n2` are the counts of unique numbers in `nums1` and `nums2` respectively, the space complexity of the code can be estimated as `O(n1 + n2)`.

Furthermore, a constant amount of space is used for the counters `a`, `b`, `c`, `x`, `y`, and `ans`, which does not depend on the input size and thus does not significantly affect the overall space complexity.

Therefore, the space complexity remains `O(n1 + n2)`.

๐
Become an
Algo Monster

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ
โTA ๐จโ๐ซ