1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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
}
|