leetcode

commit 742b30815093cad3976242201267c62f3e99b215
parent f0d62fda0a83822978791fd4294198515836e654
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat, 27 Jun 2026 09:08:59 -0600

3020. find the maximum number of elements in subset

Diffstat:
A
find_max_num_elem_subset.c
 | 
73
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
find_max_num_elem_subset.py
 | 
33
+++++++++++++++++++++++++++++++++

2 files changed, 106 insertions(+), 0 deletions(-)
diff --git a/find_max_num_elem_subset.c b/find_max_num_elem_subset.c
@@ -0,0 +1,73 @@
+// 3020. Find the Maximum Number of Elements in Subset
+#include "leetcode.h"
+
+/*
+ * you are given an array of positive integers 'nums'. you need to select a
+ * subset of 'nums' which satisfies the following condition: you can place the
+ * selected elements in a 0-indexed array such that it follows the pattern '[x,
+ * x2, x4, ..., k k/2]'. return the maximum nnumber of elements in a subset that
+ * satisfies these conditions.
+ */
+
+int cmp(const void *a, const void *b) {
+  int aa = *(int *)a, bb = *(int *)b;
+  return (aa > bb) - (aa < bb);
+}
+
+int lower_bound(int *nums, int n, long long target) {
+  int l = 0, r = n;
+  while (l < r) {
+    int mid = l + (r - l) / 2;
+    if ((long long)nums[mid] < target)
+      l = mid + 1;
+    else
+      r = mid;
+  }
+  return l;
+}
+
+int get_cnt(int *nums, int n, long long target) {
+  int left = lower_bound(nums, n, target);
+  int right = lower_bound(nums, n, target + 1);
+  return right - left;
+}
+
+bool exists(int *nums, int n, long long target) {
+  int pos = lower_bound(nums, n, target);
+  return pos < n && (long long)nums[pos] == target;
+}
+
+int maximumLength(int *nums, int numsSize) {
+  qsort(nums, numsSize, sizeof(int), cmp);
+  int ans = 0;
+  for (int i = 0; i < numsSize; i++) {
+    if (i > 0 && nums[i] == nums[i - 1])
+      continue;
+    long long key = nums[i];
+    int total = 0;
+    if (key == 1) {
+      int cnt = get_cnt(nums, numsSize, 1);
+      total = (cnt % 2 == 1) ? cnt : cnt - 1;
+    } else {
+      while (get_cnt(nums, numsSize, key) >= 2 && key <= LLONG_MAX / key &&
+             exists(nums, numsSize, key * key)) {
+        total += 2;
+        key *= key;
+      }
+      total++;
+    }
+    ans = fmax(ans, total);
+  }
+  return ans;
+}
+
+int main() {
+  int n1[] = {5, 4, 1, 2, 2};
+  int n2[] = {1, 3, 2, 4};
+  int r1 = maximumLength(n1, ARRAY_SIZE(n1));
+  int r2 = maximumLength(n2, ARRAY_SIZE(n2));
+  printf("%d\n", r1);
+  assert(r1 == 3);
+  printf("%d\n", r2);
+  assert(r2 == 1);
+}
diff --git a/find_max_num_elem_subset.py b/find_max_num_elem_subset.py
@@ -0,0 +1,33 @@
+# 3020. Find the Maximum Number of Elements in Subset
+
+"""
+you are given an array of positive integers 'nums'. you need to select a
+subset of 'nums' which satisfies the following condition: you can place the
+selected elements in a 0-indexed array such that it follows the pattern '[x,
+x2, x4, ..., k k/2]'. return the maximum nnumber of elements in a subset that
+satisfies these conditions.
+"""
+
+from collections import Counter
+
+
+class Solution:
+    def maximumLength(self, nums: List[int]) -> int:
+        cnt, ans = Counter(nums), 0
+        for key in cnt.keys():
+            if key == 1:
+                total = cnt[key] if cnt[key] % 2 else cnt[key] - 1
+            else:
+                total = 0
+                while cnt[key] >= 2 and key * key in cnt:
+                    total += 2
+                    key = key * key
+                total += 1
+            ans = max(ans, total)
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.maximumLength(nums=[5, 4, 1, 2, 2]))
+    print(obj.maximumLength(nums=[1, 3, 2, 4]))