leetcode

commit 1aaf4fd380c221dfa2ed7e03d23d663214678893
parent 675024decebe2a0bee4fe08ff5d635fe20ea061c
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu, 26 Feb 2026 20:56:34 -0700

3666. minimum operations to equalise binary string

Diffstat:
A
min_ops_equal_bin_str.c
 | 
53
+++++++++++++++++++++++++++++++++++++++++++++++++++++
A
min_ops_equal_bin_str.py
 | 
35
+++++++++++++++++++++++++++++++++++

2 files changed, 88 insertions(+), 0 deletions(-)
diff --git a/min_ops_equal_bin_str.c b/min_ops_equal_bin_str.c
@@ -0,0 +1,53 @@
+// 3666. Minimum Operations to Equalize Binary String
+#include "leetcode.h"
+
+/*
+ * you are given a binary string 's' and an integer 'k'. in one operation, you
+ * mut choose exactly 'k' difference indices and flip each '0' to '1' and each
+ * '1' to '0'. return the minimum number of operations required to make all
+ * characters in the string equal to '1'. if it is not possible, return -1.
+ */
+
+int ceil_div(int x, int y) { return (x + y - 1) / y; }
+
+int minOperations(char *s, int k) {
+  int n = strlen(s), z = 0, ans = INT_MAX;
+  for (int i = 0; i < n; i++)
+    if (s[i] == '0')
+      z++;
+  if (n == k) {
+    if (!z)
+      return 0;
+    if (z == n)
+      return 1;
+    return -1;
+  }
+  if (!(z % 2)) {
+    int m = ceil_div(z, k), tmp = ceil_div(z, n - k);
+    m = fmax(m, tmp);
+    if (m % 2 == 1)
+      m++;
+    ans = fmin(ans, m);
+  }
+  if (z % 2 == k % 2) {
+    int m = ceil_div(z, k), tmp = ceil_div(n - z, n - k);
+    m = fmax(m, tmp);
+    if (!(m % 2))
+      m++;
+    ans = fmin(ans, m);
+  }
+  return ans == INT_MAX ? -1 : ans;
+}
+
+int main() {
+  char *s1 = "110", *s2 = "0101", *s3 = "101";
+  int r1 = minOperations(s1, 1);
+  int r2 = minOperations(s2, 3);
+  int r3 = minOperations(s3, 2);
+  printf("%d\n", r1);
+  assert(r1 == 1);
+  printf("%d\n", r2);
+  assert(r2 == 2);
+  printf("%d\n", r3);
+  assert(r3 == -1);
+}
diff --git a/min_ops_equal_bin_str.py b/min_ops_equal_bin_str.py
@@ -0,0 +1,35 @@
+# 3666. Minimum Operations to Equalize Binary String
+
+"""
+you are given a binary string 's' and an integer 'k'. in one operation, you
+mut choose exactly 'k' difference indices and flip each '0' to '1' and each
+'1' to '0'. return the minimum number of operations required to make all
+characters in the string equal to '1'. if it is not possible, return -1.
+"""
+
+
+def ceil_div(x: int, y: int) -> int:
+    return (x + y - 1) // y
+
+
+class Solution:
+    def minOperations(self, s: str, k: int) -> int:
+        n, z, ans = len(s), s.count("0"), float("inf")
+        if n == k:
+            return 0 if z == 0 else 1 if z == n else -1
+        if z % 2 == 0:
+            m = max(ceil_div(z, k), ceil_div(z, n - k))
+            m += m & 1
+            ans = min(ans, m)
+        if z % 2 == k % 2:
+            m = max(ceil_div(z, k), ceil_div(n - z, n - k))
+            m += m & 1 == 0
+            ans = min(ans, m)
+        return ans if ans < float("inf") else -1
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.minOperations(s="110", k=1))
+    print(obj.minOperations(s="0101", k=3))
+    print(obj.minOperations(s="101", k=2))