Funnel Division Medium · Topics · Company Tags · Hints
You are given a list of positive integers arranged in strictly increasing order. Your task is to partition this list into several groups called "funnels." Within each funnel, the elements must be in strictly decreasing order when multiplied together in a multiplicative sequence. Moreover, every funnel must contain the exact same number of elements.
A multiplicative sequence means that each subsequent integer in the funnel is the product of the previous integer and some fixed factor, and this factor is consistent within the funnel. The smallest value in one funnel must equal the product of the largest value in the next funnel multiplied by that same factor.
Implement a function that performs this division and returns the list of funnels.
Example 1:
Input: sorted_list = [2, 4, 8, 16, 32, 64]
Output: [[64, 32, 16], [8, 4, 2]]
Explanation: Two funnels, each with three elements. The first funnel decreasing multiplicatively (each element is half the previous), and its minimum 16 multiplied by 0.5 gives 8, which is the maximum of the second funnel.
Example 2:
Input: sorted_list = [3, 9, 27, 81, 243, 729]
Output: [[729, 243, 81], [27, 9, 3]]
Example 3:
Input: sorted_list = [5, 25, 125]
Output: [[125, 25, 5]]
Constraints:
1 <= sorted_list.length <= 100,000sorted_list are strictly increasing positive values.