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.

Learn more about Math and Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's fasterIt has better space complexityOrder of computer subproblems does not matterIt has better time complexity

I don’t know

Solution Approach

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

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.
Initialization: The code then initializes an ans variable to accumulate the count of the triplets.
Iterating through the arrays:
- For each unique numbera 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.
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]).
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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

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 binnums2) * 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.

Solution Implementation

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

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

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

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

Not Sure What to Study? Take the 2-min Quiz：

Which of these pictures shows the visit order of a depth-first search?

I don’t know

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).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

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

Problem Description

Intuition

Solution Approach

Example Walkthrough

Step 1: Count Frequencies

Step 2: Initialization

Step 3: Iterating through the arrays

Step 4: Combination Logic

Step 5: Double Counting Adjustment

Solution Implementation