#2501
Longest Square Streak in an Array
specialist · 820 · lc medium +31 · verified · 53.1% accepted · 1,008 likes · top 44%
Description
Given an integer array nums, find the longest "square streak" subsequence: a subsequence of length ≥ 2 where, when sorted, every element after the first is the square of the preceding element. Return the length of the longest such streak, or -1 if none exists.
Example 1:
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.
Example 2:
Input: nums = [2,3,5,6,7]
Output: -1
Explanation: There is no square streak in nums so return -1.
Code
1
2
3