Longest Square Streak in an Array
Problem
A subsequence of nums is a square streak if it has length at least 2 and, after sorting, every element except the first equals the square of the element before it. Return the length of the longest square streak, or -1 if none exists.
nums = [4,3,6,16,8,2]3nums = [2,3,5,6,7]-1def longest_square_streak(nums):
s = set(nums)
best = -1
for n in nums:
length = 0
cur = n
while cur in s:
length += 1
cur = cur * cur
if length >= 2:
best = max(best, length)
return bestfunction longestSquareStreak(nums) {
const s = new Set(nums);
let best = -1;
for (const n of nums) {
let length = 0;
let cur = n;
while (s.has(cur)) {
length++;
cur = cur * cur;
}
if (length >= 2) best = Math.max(best, length);
}
return best;
}int longestSquareStreak(int[] nums) {
Set<Long> s = new HashSet<>();
for (int n : nums) s.add((long) n);
int best = -1;
for (int n : nums) {
int length = 0;
long cur = n;
while (s.contains(cur)) {
length++;
cur = cur * cur;
}
if (length >= 2) best = Math.max(best, length);
}
return best;
}int longestSquareStreak(vector<int>& nums) {
unordered_set<long long> s(nums.begin(), nums.end());
int best = -1;
for (int n : nums) {
int length = 0;
long long cur = n;
while (s.count(cur)) {
length++;
cur = cur * cur;
}
if (length >= 2) best = max(best, length);
}
return best;
}Explanation
A square streak is just a chain x → x² → x⁴ → … where every value on the chain is actually present in nums. Sorting a subsequence and demanding each element be the square of the previous one is exactly the same as following such a chain upward, so we never have to sort or enumerate subsequences at all.
First we drop every value into a hash set s so membership tests are O(1). Then for each starting value n we walk the chain: start with cur = n and, as long as cur is in the set, count it and replace cur with cur². The number of values we visited before falling out of the set is the streak length starting at n.
A streak only counts if its length is at least 2 (a single element is not a valid square streak). Among all qualifying streaks we keep the maximum; if none reaches length 2 we return -1.
Because values are at most 10⁵, each chain can grow at most a handful of times before squaring exceeds the bound (10⁵ → 10¹⁰ already escapes), so every chain walk is effectively O(log log max) — a tiny constant. We use 64-bit integers for cur in Java and C++ so the square does not overflow before the membership test fails.
Example: nums = [4,3,6,16,8,2]. Starting at 2 the chain is 2 → 4 → 16 → 256; 2, 4, 16 are present but 256 is not, giving length 3. No other start beats it, so the answer is 3.