diff options
-rw-r--r-- | find_kth_bit_nth_bin_str.c | 30 | ||||
-rw-r--r-- | find_kth_bit_nth_bin_str.py | 34 |
2 files changed, 64 insertions, 0 deletions
diff --git a/find_kth_bit_nth_bin_str.c b/find_kth_bit_nth_bin_str.c new file mode 100644 index 0000000..c3fa6a5 --- /dev/null +++ b/find_kth_bit_nth_bin_str.c @@ -0,0 +1,30 @@ +// 1545. Find Kth Bit in Nth Binary String +#include "leetcode.h" + +/* + * given two positive integers 'n' and 'k', the binary string 's_n' is formed as + * follows: 's_1 = 0', 's_i = s_i - 1 + "1" + reverse(invert(s_i - 1))' for 'i > + * 1'. where '+' denotes the concatenation operation, 'reverse(x)' returns the + * reversed string 'x', and 'invert(x)' inverts all teh bits in 'x'. return the + * k'th bit in 's_n'. it is guaranteed that 'k' is valid for the given 'n'. + */ + +int max_bit(int n) { + while ((n & (n - 1))) + n &= n - 1; + return n; +} + +char findKthBit(int n, int k) { + int inv = 0; + while (k & (k - 1)) { + k = -k & (max_bit(k) - 1); + inv ^= 1; + } + return ((k > 1) ^ inv) + '0'; +} + +int main() { + printf("%c\n", findKthBit(3, 1)); // expect: 0 + printf("%c\n", findKthBit(4, 11)); // expect: 1 +} diff --git a/find_kth_bit_nth_bin_str.py b/find_kth_bit_nth_bin_str.py new file mode 100644 index 0000000..afcac24 --- /dev/null +++ b/find_kth_bit_nth_bin_str.py @@ -0,0 +1,34 @@ +# 1545. Find Kth Bit in Nth Binary String + +""" +given two positive integers 'n' and 'k', the binary string 's_n' is formed as +follows: 's_1 = 0', 's_i = s_i - 1 + "1" + reverse(invert(s_i - 1))' for 'i > +1'. where '+' denotes the concatenation operation, 'reverse(x)' returns the +reversed string 'x', and 'invert(x)' inverts all teh bits in 'x'. return the +k'th bit in 's_n'. it is guaranteed that 'k' is valid for the given 'n'. +""" + + +class Solution(object): + def findKthBit(self, n, k): + """ + :type n: int + :type k: int + :rtype: str + """ + flip = 0 + inv = 2**n - 1 + while k > 1: + if k == inv / 2 + 1: + return str(1 ^ flip) + if k > inv / 2: + k = inv + 1 - k + flip = 1 - flip + inv /= 2 + return str(flip) + + +if __name__ == "__main__": + obj = Solution() + print(obj.findKthBit(3, 1)) + print(obj.findKthBit(4, 11)) |