Sponsored
Sponsored
This approach leverages a HashSet for quick access to elements and checks subsequent squares in the sequence. We iterate over each number in the array, and for each number, keep finding its squares while incrementing the length of the streak. The longest streak is tracked and returned at the end.
Time Complexity: O(n^1.5) in worst-case due to nested loops and nested search.
Space Complexity: O(1) extra space for auxiliary storage as in-place checks are performed.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5bool contains(int* set, int setSize, int num) {
6 for (int i = 0; i < setSize; ++i) {
7 if (set[i] == num) return true;
8 }
9 return false;
10}
11
12int squareStreak(int* nums, int numsSize) {
13 int maxLength = -1;
14 for (int i = 0; i < numsSize; ++i) {
15 int num = nums[i];
16 int length = 1;
17 int current = num;
18 while (contains(nums, numsSize, current * current)) {
19 ++length;
20 current *= current;
21 }
22 if (length > 1) {
23 maxLength = (length > maxLength) ? length : maxLength;
24 }
25 }
26 return maxLength;
27}
28
29int main() {
30 int nums[] = {4, 3, 6, 16, 8, 2};
31 int numsSize = sizeof(nums) / sizeof(nums[0]);
32 printf("%d\n", squareStreak(nums, numsSize));
33 return 0;
34}The program begins by defining a helper function contains to determine if a squared value exists in the array. Then, for each element in the array, it calculates the squares sequentially. It keeps track of the maximum streak length, which is updated whenever a longer streak is found.
This approach uses dynamic programming to store intermediate results regarding the longest square streak ending at each number. Sorting the array helps in ensuring that every subsequent square evaluated is in a larger-than relationship compared to previous elements, thus contributing to the streak length.
Time Complexity: O(n^2) due to nested loops used in the calculation of dp array.
Space Complexity: O(n) for managing the dp array.
1
public class LongestSquareStreakDP {
public static int LongestSquareStreak(int[] nums) {
Array.Sort(nums);
int[] dp = new int[nums.Length];
Array.Fill(dp, 1);
int maxLength = -1;
for (int i = 0; i < nums.Length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] == nums[j] * nums[j]) {
dp[i] = Math.Max(dp[i], dp[j] + 1);
}
}
if (dp[i] > 1) {
maxLength = Math.Max(maxLength, dp[i]);
}
}
return maxLength;
}
public static void Main() {
int[] nums = {4, 3, 6, 16, 8, 2};
Console.WriteLine(LongestSquareStreak(nums));
}
}The C# uses a sorted array followed by a fillable dp array. This dynamic technique efficiently finds the square streak by updating dp based on squared number progression.