Back to all solutions
#1545 - Find Kth Bit in Nth Binary String
Problem Description
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)) for i > 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 four 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.
Solution
/**
* @param {number} n
* @param {number} k
* @return {character}
*/
var findKthBit = function(n, k) {
let position = k - 1;
let invertCount = 0;
let length = (1 << n) - 1;
while (position !== 0) {
const mid = length >> 1;
if (position === mid) {
return invertCount % 2 === 0 ? '1' : '0';
}
if (position > mid) {
position = length - position - 1;
invertCount++;
} else {
length = mid;
}
}
return invertCount % 2 === 0 ? '0' : '1';
};