aboutsummaryrefslogtreecommitdiff
path: root/find_kth_bit_nth_bin_str.py
diff options
context:
space:
mode:
Diffstat (limited to 'find_kth_bit_nth_bin_str.py')
-rw-r--r--find_kth_bit_nth_bin_str.py34
1 files changed, 34 insertions, 0 deletions
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))