longest_square_streak_arr.py (1142B)
| # 2501. Longest Square Streak in an Array
from math import isqrt
"""
you are given an integer array 'nums'. a subsequence of 'nums' is called a
square streak if the length of the subsequence is at least 2 and after
sorting the subsequence, each element (except the first element) is the
square of the previous number. return the length of the longest square streak
in 'nums', or '-1' otherwise. 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.
"""
class Solution(object):
def longestSquareStreak(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
mp, ans = {}, -1
nums.sort()
for i in nums:
sqrt = isqrt(i)
if sqrt * sqrt == i and sqrt in mp:
mp[i] = mp[sqrt] + 1
ans = max(ans, mp[i])
else:
mp[i] = 1
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.longestSquareStreak(nums=[4, 3, 6, 16, 8, 2]))
print(obj.longestSquareStreak(nums=[2, 3, 5, 6, 7]))
|
