aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-14 23:27:18 -0600
committerJack Sangdahl <[email protected]>2024-10-14 23:27:18 -0600
commit27af057186aceb596325e3b0b21d03ea962d51df (patch)
treec3aa3586510f8a505bb22935e6f884ab6295b7f5
parent001657e7e896dcee47903d25e177018a63e26ebe (diff)
downloadleetcode-27af057186aceb596325e3b0b21d03ea962d51df.tar.gz
leetcode-27af057186aceb596325e3b0b21d03ea962d51df.zip
2938. separate black and white balls
-rw-r--r--separate_black_white_balls.c27
-rw-r--r--separate_black_white_balls.py30
2 files changed, 57 insertions, 0 deletions
diff --git a/separate_black_white_balls.c b/separate_black_white_balls.c
new file mode 100644
index 0000000..340e539
--- /dev/null
+++ 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
new file mode 100644
index 0000000..d492854
--- /dev/null
+++ 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"))