aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--find_kth_bit_nth_bin_str.c30
-rw-r--r--find_kth_bit_nth_bin_str.py34
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))