You are shopping on Amazon.com for some bags of rice. Each listing displays the number
of grains of rice that the bag contains. You want to buy a perfect set of rice bags.
From the entire search results list, riceBags. A perfect set of rice bags,
perfect, is defined as:
perfect are sorted in increasing order by grain count,
it satisfies the condition perfect[i] * perfect[i] = perfect[i+1] for all 1 ≤ i < n.
Here perfect[i] is the size of the set and perfect[i] is the number of rice grains
in bag i.
Find the largest possible set perfect and return an integer, the size of that set. If no such set
is possible, then return -1. It is guaranteed that all elements in riceBags are distinct.
Function Description
Complete the function maxSetSize in the editor.
maxSetSize has the following parameter:
int riceBags[n]: the list of bags of rice by rice grain counts
Returns
int: the size of the largest set possible or -1 if there is none
ᯓ★ ꒰ა Credit to Nick ໒꒱ ᯓᡣ𐭩
Example 1:
Input: riceBags = [625, 4, 2, 5, 25]
Output: 3
Explanation:All of the possible perfect sets: - [625, 25] - [4, 2] - [5, 25] - [625, 5, 25] The largest perfect set has size 3.
Example 2:
Input: riceBags = [3, 9, 4, 2, 16]
Output: 3
Explanation:Let the bags of rice available on Amazon have grain counts [3, 9, 4, 2, 16]. The following are the perfect sets: Set perfect = [3, 9]. The size of this set is 2. Set perfect = [4, 2]. The size of this set is 2. Set perfect = [4, 16]. The size of this set is 2. Set perfect = [4, 2, 16]. The size of this set is 3. The size of the largest set is 3. The image above illustrates the correct ordering of the purchased rice bags by grains of rice.
1 ≤ n ≤ 2 × 105
2 ≤ riceBags[i] ≤ 106
input:
output: