diff options
Diffstat (limited to 'longest_square_streak_arr.c')
-rw-r--r-- | longest_square_streak_arr.c | 53 |
1 files changed, 53 insertions, 0 deletions
diff --git a/longest_square_streak_arr.c b/longest_square_streak_arr.c new file mode 100644 index 0000000..90ca314 --- /dev/null +++ b/longest_square_streak_arr.c @@ -0,0 +1,53 @@ +// 2501. Longest Square Streak in an Array +#include "leetcode.h" + +/* + * 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. + */ + +int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } + +bool search(long long *nums, int numsSize, long long target) { + int l = 0, h = numsSize - 1; + while (l <= h) { + int m = l + (h - l) / 2; + if (nums[m] == target) + return true; + if (nums[m] < target) + l = m + 1; + else + h = m - 1; + } + return false; +} + +int longestSquareStreak(int *nums, int numsSize) { + qsort(nums, numsSize, sizeof(int), cmp); + long long *stk = (long long *)malloc(numsSize * sizeof(long long)); + for (int i = 0; i < numsSize; ++i) + stk[i] = nums[i]; + long long ans = -1; + for (int i = 0; i < numsSize; ++i) { + long long val = (long long)nums[i], cnt = 1; + while (search(stk, numsSize, val * val)) { + val *= val; + cnt++; + } + if (cnt > 1 && ans < cnt) + ans = cnt; + } + free(stk); + return (int)ans; +} + +int main() { + int n1[] = {4, 3, 6, 16, 8, 2}, n2[] = {2, 3, 5, 6, 7}; + printf("%d\n", longestSquareStreak(n1, ARRAY_SIZE(n1))); // expect: 3 + printf("%d\n", longestSquareStreak(n2, ARRAY_SIZE(n2))); // expect: -1 +} |