diff options
-rw-r--r-- | num_times_binary_string_aligned.c | 30 | ||||
-rw-r--r-- | num_times_binary_string_aligned.py | 31 |
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])) |