find-the-maximum-number-of-elements-in-subset

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

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

You need to select a subset of <code>nums</code> which satisfies the following condition:

<ul>
	<li>You can place the selected elements in a 0-indexed array such that it follows the pattern: <code>[x, x2, x4, ..., xk/2, xk, xk/2, ..., x4, x2, x]</code> (Note that <code>k</code> can be&nbsp;any non-negative 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>

Return the maximum number of elements in a subset that satisfies these conditions.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
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. 
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>

第 382 场周赛

weekly-contest-382

maximumLength

高级工程师

Find the Maximum Number of Elements in Subset

Longest Consecutive Sequence

longest-consecutive-sequence

最长连续序列

Array

Hash Table

Enumeration

给你一个 正整数 数组 <code>nums</code> 。

你需要从数组中选出一个满足下述条件的子集：

<ul>
	<li>你可以将选中的元素放置在一个下标从 0 开始的数组中，并使其遵循以下模式：<code>[x, x2, x4, ..., xk/2, xk, xk/2, ..., x4, x2, x]</code>（注意，<code>k</code> 可以是任何 非负 的 2 的幂）。例如，<code>[2, 4, 16, 4, 2]</code> 和 <code>[3, 9, 3]</code> 都符合这一模式，而 <code>[2, 4, 8, 4, 2]</code> 则不符合。</li>
</ul>

返回满足这些条件的子集中，元素数量的 最大值 。

&nbsp;

示例 1：

<pre>
输入：nums = [5,4,1,2,2]
输出：3
解释：选择子集 {4,2,2} ，将其放在数组 [2,4,2] 中，它遵循该模式，且 22 == 4 。因此答案是 3 。
</pre>

示例 2：

<pre>
输入：nums = [1,3,2,4]
输出：1
解释：选择子集 {1}，将其放在数组 [1] 中，它遵循该模式。因此答案是 1 。注意我们也可以选择子集 {2} 、{4} 或 {3} ，可能存在多个子集都能得到相同的答案。
</pre>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>