diff options
author | Jack Sangdahl <[email protected]> | 2024-10-27 21:31:44 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-27 21:31:44 -0600 |
commit | 6f48fe464b740f4bf8d680d70ce784467a1e3d9c (patch) | |
tree | ece63ad19dcbccd306986c68958a62f7639dd65b | |
parent | 2026181648f9a947f6ba9cac7f8497579010d278 (diff) | |
download | leetcode-6f48fe464b740f4bf8d680d70ce784467a1e3d9c.tar.gz leetcode-6f48fe464b740f4bf8d680d70ce784467a1e3d9c.zip |
2501. longest square streak in an array
-rw-r--r-- | longest_square_streak_arr.c | 53 | ||||
-rw-r--r-- | longest_square_streak_arr.py | 36 |
2 files changed, 89 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 +} diff --git a/longest_square_streak_arr.py b/longest_square_streak_arr.py new file mode 100644 index 0000000..795bf33 --- /dev/null +++ b/longest_square_streak_arr.py @@ -0,0 +1,36 @@ +# 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])) |