aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-27 21:31:44 -0600
committerJack Sangdahl <[email protected]>2024-10-27 21:31:44 -0600
commit6f48fe464b740f4bf8d680d70ce784467a1e3d9c (patch)
treeece63ad19dcbccd306986c68958a62f7639dd65b
parent2026181648f9a947f6ba9cac7f8497579010d278 (diff)
downloadleetcode-6f48fe464b740f4bf8d680d70ce784467a1e3d9c.tar.gz
leetcode-6f48fe464b740f4bf8d680d70ce784467a1e3d9c.zip
2501. longest square streak in an array
-rw-r--r--longest_square_streak_arr.c53
-rw-r--r--longest_square_streak_arr.py36
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]))