aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--num_times_binary_string_aligned.c30
-rw-r--r--num_times_binary_string_aligned.py31
2 files changed, 61 insertions, 0 deletions
diff --git a/num_times_binary_string_aligned.c b/num_times_binary_string_aligned.c
new file mode 100644
index 0000000..9d5effa
--- /dev/null
+++ b/num_times_binary_string_aligned.c
@@ -0,0 +1,30 @@
+// 1375. Number of Times Binary String Is Prefix-Aligned
+#include "leetcode.h"
+
+/*
+ * you have a 1 indexed binary string of length 'n' where all the bits are 0
+ * initially. we will flip all the bits of this binary string one by one. you
+ * are given a 1 indexed integer array 'flips' where 'flips[i]' indicates that
+ * the bit at index 'i' will be flipped in the i'th step. a binar y string is
+ * prefix aligned if after the i'th step, all the bits in the inclusive range
+ * '[1, i]' are ones and all the other bits are zeros. return the number of
+ * times the binary string is prefix aligned during the flipping process.
+ */
+
+int numTimesAllBlue(int *flips, int flipsSize) {
+ int max = -1, num = 0, ans = 0;
+ for (int i = 0; i < flipsSize; i++) {
+ num++;
+ if (flips[i] > max)
+ max = flips[i];
+ if (max == num)
+ ans++;
+ }
+ return ans;
+}
+
+int main() {
+ int f1[] = {3, 2, 4, 1, 5}, f2[] = {4, 1, 2, 3};
+ printf("%d\n", numTimesAllBlue(f1, ARRAY_SIZE(f1))); // expect: 2
+ printf("%d\n", numTimesAllBlue(f2, ARRAY_SIZE(f2))); // expect: 1
+}
diff --git a/num_times_binary_string_aligned.py b/num_times_binary_string_aligned.py
new file mode 100644
index 0000000..481c894
--- /dev/null
+++ b/num_times_binary_string_aligned.py
@@ -0,0 +1,31 @@
+# 1375. Number of Times Binary String Is Prefix-Aligned
+
+"""
+you have a 1 indexed binary string of length 'n' where all the bits are 0
+initially. we will flip all the bits of this binary string one by one. you
+are given a 1 indexed integer array 'flips' where 'flips[i]' indicates that
+the bit at index 'i' will be flipped in the i'th step. a binar y string is
+prefix aligned if after the i'th step, all the bits in the inclusive range
+'[1, i]' are ones and all the other bits are zeros. return the number of
+times the binary string is prefix aligned during the flipping process.
+"""
+
+
+class Solution(object):
+ def numTimesAllBlue(self, flips):
+ """
+ :type flips: List[int]
+ :rtype: int
+ """
+ ans, state = 0, 0
+ for i in flips:
+ state = state | (1 << (i - 1))
+ if state & (state + 1) == 0:
+ ans += 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numTimesAllBlue([3, 2, 4, 1, 5]))
+ print(obj.numTimesAllBlue([4, 1, 2, 3]))