longest-square-streak-in-an-array

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>nums</code>. A subsequence of <code>nums</code> is called a square streak if:

<ul>
	<li>The length of the subsequence is at least <code>2</code>, and</li>
	<li>after sorting the subsequence, each element (except the first element) is the square of the previous number.</li>
</ul>

Return the length of the longest square streak in <code>nums</code>, or return <code>-1</code> if there is no square streak.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

&nbsp;
Example 1:

<pre>
Input: nums = [4,3,6,16,8,2]
Output: 3
Explanation: Choose the subsequence [4,16,2]. After sorting it, it becomes [2,4,16].
- 4 = 2 * 2.
- 16 = 4 * 4.
Therefore, [4,16,2] is a square streak.
It can be shown that every subsequence of length 4 is not a square streak.
</pre>

Example 2:

<pre>
Input: nums = [2,3,5,6,7]
Output: -1
Explanation: There is no square streak in nums so return -1.
</pre>

&nbsp;
Constraints:

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

longestSquareStreak

Longest Square Streak in an Array

Array

Hash Table

Binary Search

Dynamic Programming

Sorting

给你一个整数数组 <code>nums</code> 。如果 <code>nums</code> 的子序列满足下述条件，则认为该子序列是一个 方波 ：

<ul>
	<li>子序列的长度至少为 <code>2</code> ，并且</li>
	<li>将子序列从小到大排序 之后 ，除第一个元素外，每个元素都是前一个元素的 平方 。</li>
</ul>

返回 <code>nums</code> 中 最长方波 的长度，如果不存在 方波 则返回 <code>-1</code> 。

子序列 也是一个数组，可以由另一个数组删除一些或不删除元素且不改变剩余元素的顺序得到。

&nbsp;

示例 1 ：

<pre>输入：nums = [4,3,6,16,8,2]
输出：3
解释：选出子序列 [4,16,2] 。排序后，得到 [2,4,16] 。
- 4 = 2 * 2.
- 16 = 4 * 4.
因此，[4,16,2] 是一个方波.
可以证明长度为 4 的子序列都不是方波。
</pre>

示例 2 ：

<pre>输入：nums = [2,3,5,6,7]
输出：-1
解释：nums 不存在方波，所以返回 -1 。
</pre>

&nbsp;

提示：

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