#3020

Find the Maximum Number of Elements in Subset

expert · 1155 · lc medium +32 · verified · 26.9% accepted · 217 likes · top 5%

Description

You are given an array of positive integers nums.

Select a subset that can be arranged as [x, x², x⁴, ..., x^k/2, x^k, x^k/2, ..., x⁴, x², x] for some non-negative power-of-2 exponent k. For example, [2, 4, 16, 4, 2] and [3, 9, 3] satisfy this pattern, but [2, 4, 8, 4, 2] does not.

Return the maximum number of elements in such a subset.

Example 1:

Input: nums = [5,4,1,2,2]

Output: 3

Explanation: We can select the subset {4,2,2}, which can be placed in the array as [2,4,2] which follows the pattern and 22 == 4. Hence the answer is 3.

Example 2:

Input: nums = [1,3,2,4]

Output: 1

Explanation: 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.

Code

1

2

3

class Solution:
    def maximumLength(self, nums: List[int]) -> int:

class Solution:
    def maximumLength(self, nums: List[int]) -> int: