Given two positive integers n and k, the binary string Sn is formed as follows:
S1 = "0"Si = Si-1 + "1" + reverse(invert(Si-1))fori > 1
Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).
For example, the first 4 strings in the above sequence are:
S1 = "0"S2 = "011"S3 = "0111001"S4 = "011100110110001"
Return the kth bit in Sn. It is guaranteed that k is valid for the given n.
Example 1:
Input: n = 3, k = 1 Output: "0" Explanation: S3 is "0111001". The first bit is "0".
Example 2:
Input: n = 4, k = 11 Output: "1" Explanation: S4 is "011100110110001". The 11th bit is "1".
Example 3:
Input: n = 1, k = 1 Output: "0"
Example 4:
Input: n = 2, k = 3 Output: "1"
Constraints:
1 <= n <= 201 <= k <= 2n - 1
Solution 1: Brute Force / Simulation
Generate the string till Sn or length >= k.
Time complexity: O(2^n)
Space complexity: O(2^n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: char findKthBit(int n, int k) { string ans = "0"; for (int i = 2; i <= n && ans.length() < k; ++i) { string tmp(rbegin(ans), rend(ans)); for (char& c : tmp) c = '1' - c + '0'; ans = ans + "1" + tmp; } return ans[k - 1]; } }; |
Solution 2: Recursion
All the strings have odd length of L = (1 << n) – 1,
Let say the center m = (L + 1) / 2
if n == 1, k should be 1 and ans is “0”.
Otherwise
if k == m, we know it’s “1”.
if k < m, the answer is the same as find(n-1, K)
if k > m, we are finding a flipped and mirror char in S(n-1), thus the answer is flip(find(n-1, L – k + 1)).
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: char findKthBit(int n, int k) { if (n == 1) return '0'; int l = (1 << n) - 1; if (k == (l + 1) / 2) return '1'; else if (k < (l + 1) / 2) return findKthBit(n - 1, k); else return '1' - findKthBit(n - 1, l - k + 1) + '0'; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution { public char findKthBit(int n, int k) { if (n == 1) return '0'; int l = (1 << n) - 1; if (k == (l + 1) / 2) return '1'; else if (k < (l + 1) / 2) return findKthBit(n - 1, k); else return (char)('1' - findKthBit(n - 1, l - k + 1) + '0'); } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 |
class Solution: def findKthBit(self, n: int, k: int) -> str: if n == 1: return "0" l = (1 << n) - 1 if k == (l + 1) / 2: return "1" elif k < (l + 1) / 2: return self.findKthBit(n - 1, k) else: return str(1 - int(self.findKthBit(n - 1, l - k + 1))) |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment