leetcode

commit 39db6fb1c89596bba2efd036de5b4834b0f38642
parent 4e20b6830acfc87db121204b472dc0da62f4ef28
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu,  5 Feb 2026 22:22:53 -0700

3634. minimum removals to balance array

Diffstat:
A
min_removals_balance_arr.c
 | 
38
++++++++++++++++++++++++++++++++++++++
A
min_removals_balance_arr.py
 | 
34
++++++++++++++++++++++++++++++++++

2 files changed, 72 insertions(+), 0 deletions(-)
diff --git a/min_removals_balance_arr.c b/min_removals_balance_arr.c
@@ -0,0 +1,38 @@
+// 3634. Minimum Removals to Balance Array
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' and an integer 'k'. an array is
+ * considered balance if the value of its maximum element is at most 'k' times
+ * the minimum element. you may remove any number of elements from 'nums'
+ * without making it empty. return the minimum number of elements so that the
+ * remaining array is balanced. note an array of size 1 is considered to be
+ * balance as its maximum and minimum are equal, and the condition always holds
+ * true.
+ */
+
+int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
+
+int minRemoval(int *nums, int numsSize, int k) {
+  qsort(nums, numsSize, sizeof(int), cmp);
+  int left = 0, ans = 0;
+  for (int right = 0; right < numsSize; ++right) {
+    while ((long long)nums[right] > (long long)k * nums[left])
+      left++;
+    ans = fmax(ans, right - left + 1);
+  }
+  return numsSize - ans;
+}
+
+int main() {
+  int n1[] = {2, 1, 5}, n2[] = {1, 6, 2, 9}, n3[] = {4, 6};
+  int r1 = minRemoval(n1, ARRAY_SIZE(n1), 2);
+  int r2 = minRemoval(n2, ARRAY_SIZE(n2), 3);
+  int r3 = minRemoval(n3, ARRAY_SIZE(n3), 2);
+  printf("%d\n", r1);
+  assert(r1 == 1);
+  printf("%d\n", r2);
+  assert(r2 == 2);
+  printf("%d\n", r3);
+  assert(r3 == 0);
+}
diff --git a/min_removals_balance_arr.py b/min_removals_balance_arr.py
@@ -0,0 +1,34 @@
+# 3634. Minimum Removals to Balance Array
+
+"""
+you are given an integer array 'nums' and an integer 'k'. an array is
+considered balance if the value of its maximum element is at most 'k' times
+the minimum element. you may remove any number of elements from 'nums'
+without making it empty. return the minimum number of elements so that the
+remaining array is balanced. note an array of size 1 is considered to be
+balance as its maximum and minimum are equal, and the condition always holds
+true.
+"""
+
+
+class Solution(object):
+    def minRemoval(self, nums, k):
+        """
+        :type nums: List[int]
+        :type k: int
+        :rtype: int
+        """
+        nums.sort()
+        n, ans, left = len(nums), 0, 0
+        for right in range(n):
+            while nums[right] > k * nums[left]:
+                left += 1
+            ans = max(ans, right - left + 1)
+        return n - ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.minRemoval(nums=[2, 1, 5], k=2))
+    print(obj.minRemoval(nums=[1, 6, 2, 9], k=3))
+    print(obj.minRemoval(nums=[4, 6], k=2))