<p>You are given an array of <strong>positive</strong> integers <code>nums</code>.</p>

<p>You need to select a <span data-keyword="subset">subset</span> of <code>nums</code> which satisfies the following condition:</p>

<ul>
	<li>You can place the selected elements in a <strong>0-indexed</strong> array such that it follows the pattern: <code>[x, x<sup>2</sup>, x<sup>4</sup>, ..., x<sup>k/2</sup>, x<sup>k</sup>, x<sup>k/2</sup>, ..., x<sup>4</sup>, x<sup>2</sup>, x]</code> (<strong>Note</strong> that <code>k</code> can be be any <strong>non-negative</strong> power of <code>2</code>). For example, <code>[2, 4, 16, 4, 2]</code> and <code>[3, 9, 3]</code> follow the pattern while <code>[2, 4, 8, 4, 2]</code> does not.</li>
</ul>

<p>Return <em>the <strong>maximum</strong> number of elements in a subset that satisfies these conditions.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,4,1,2,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can select the subset {4,2,2}, which can be placed in the array as [2,4,2] which follows the pattern and 2<sup>2</sup> == 4. Hence the answer is 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,2,4]
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can select the subset {1}, which can be placed in the array as [1] which follows the pattern. Hence the answer is 1. Note that we could have also selected the subsets {2}, {3}, or {4}, there may be multiple subsets which provide the same answer. 
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        # positive num array
        # select subset of nums which:
            # x, x^2, x^4, ... x^k, x^k/2, ... x^4, x^2, x
            # k can be any positive power of 2

        
        # example1, [5, 4, 1, 2, 2]
        # we can pick [4, 2, 2] because we can make the array [2 4 2], which statisfied the condition
        # looks like we check if there is a number's square in the list
        # along with another copy of the value in the list

        # can we do freqency map? this way we can both check for count of number and its square

        # ex2: [1, 3, 2, 4], 
        # we can only pick [1] because 1 is the only subset that follows the pattern

        # pattern: [x], [x x^2 x] [x x^2 x^2 x]

        # so a value standing alone is a subset that satisfied the condition

        

        # so let's go with the frequency map.
        # we count the occurences of the values
        # then we have x to represent the power? 

        # we start from the lowest value
        # so we check if the value's square root is in the dictionary or not? 
        # if there is, we skip current value
        # so essentially we start from the smallest value
        # from the smallest value, we check if there is its square and it has 2 frequency count?
        # if so while loop, we have a count to represent the power
        # and continue to check if value^power is in the dictionary and value^power/2? has 2 counts
        # then keep the max of possible array

        # run time: O(n), we will check all the values because they could be potential starting value
        # space: O(n), we will convert the list into a dictionary, where potentially have 1 count of each value

        freq = Counter(nums)

        result = 1  # default result will be 1


        # we can perform work on the 1 first, by picking the odd count of 1, because 1 are square of itself
        if 1 in freq:
            result = freq[1] if freq[1] % 2 else freq[1] - 1

        for value in freq.keys():

            # skipping over the one that has sqrt, but we shouldn't skip over 1
            # because 1 is a sqrt of itself
            if value != 1:
            
                power = 2
                curCount = 1
                while (value ** power) in freq and freq[value ** (power // 2)] >= 2:             
                    power *= 2
                    curCount += 2
                
                result = max(result, curCount)
        
        return result
748