diff options
author | Jack Sangdahl <[email protected]> | 2024-10-14 23:27:18 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-14 23:27:18 -0600 |
commit | 27af057186aceb596325e3b0b21d03ea962d51df (patch) | |
tree | c3aa3586510f8a505bb22935e6f884ab6295b7f5 | |
parent | 001657e7e896dcee47903d25e177018a63e26ebe (diff) | |
download | leetcode-27af057186aceb596325e3b0b21d03ea962d51df.tar.gz leetcode-27af057186aceb596325e3b0b21d03ea962d51df.zip |
2938. separate black and white balls
-rw-r--r-- | separate_black_white_balls.c | 27 | ||||
-rw-r--r-- | 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 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")) |