aboutsummaryrefslogtreecommitdiff
path: root/find_kth_bit_nth_bin_str.c
diff options
context:
space:
mode:
Diffstat (limited to 'find_kth_bit_nth_bin_str.c')
-rw-r--r--find_kth_bit_nth_bin_str.c30
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
+}