diff options
Diffstat (limited to 'find_kth_bit_nth_bin_str.c')
-rw-r--r-- | find_kth_bit_nth_bin_str.c | 30 |
1 files changed, 30 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 +} |