leetcode

commit 27af057186aceb596325e3b0b21d03ea962d51df
parent 001657e7e896dcee47903d25e177018a63e26ebe
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon, 14 Oct 2024 23:27:18 -0600

2938. separate black and white balls

Diffstat:
A
separate_black_white_balls.c
 | 
27
+++++++++++++++++++++++++++
A
separate_black_white_balls.py
 | 
30
++++++++++++++++++++++++++++++

2 files changed, 57 insertions(+), 0 deletions(-)
diff --git a/separate_black_white_balls.c b/separate_black_white_balls.c
@@ -0,0 +1,27 @@
+// 2938. Separate Black and White Balls
+#include "leetcode.h"
+
+/*
+ * there are 'n' balls on a table, each ball has a colour black or white. you
+ * are given a 0-indexed binary string 's' of length 'n', where 1 and 0
+ * represent black and white balls respectively. in each step, you can choose
+ * two adjacent balls and swap them. return the minimum number of steps to group
+ * all the black balls to the right and all the white balls to the left
+ */
+
+long long minimumSteps(char *s) {
+  long long one_cnt = 0, swap_cnt = 0;
+  for (int i = 0; s[i] != '\0'; i++) {
+    if (s[i] == '1')
+      one_cnt++;
+    else
+      swap_cnt += one_cnt;
+  }
+  return swap_cnt;
+}
+
+int main() {
+  char *s1 = "101", *s2 = "100";
+  printf("%lld\n", minimumSteps(s1)); // expect: 1
+  printf("%lld\n", minimumSteps(s2)); // expect: 2
+}
diff --git a/separate_black_white_balls.py b/separate_black_white_balls.py
@@ -0,0 +1,30 @@
+# 2938. Separate Black and White Balls
+
+"""
+there are 'n' balls on a table, each ball has a colour black or white. you
+are given a 0-indexed binary string 's' of length 'n', where 1 and 0
+represent black and white balls respectively. in each step, you can choose
+two adjacent balls and swap them. return the minimum number of steps to group
+all the black balls to the right and all the white balls to the left
+"""
+
+
+class Solution(object):
+    def minimumSteps(self, s):
+        """
+        :type s: str
+        :rtype: int
+        """
+        one_cnt, swap_cnt = 0, 0
+        for i in range(len(s) - 1, -1, -1):
+            if s[i] == "1":
+                swap_cnt += one_cnt
+            else:
+                one_cnt += 1
+        return swap_cnt
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.minimumSteps("101"))
+    print(obj.minimumSteps("100"))