Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using core interview patterns strategy.
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 > 1Where + 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.
Example 1:
Input: n = 3, k = 1 Output: "0" Explanation: S3 is "0111001". The 1st bit is "0".
Example 2:
Input: n = 4, k = 11 Output: "1" Explanation: S4 is "011100110110001". The 11th bit is "1".
Constraints:
1 <= n <= 201 <= k <= 2n - 1Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: General problem-solving
3 1
4 11
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1545: Find Kth Bit in Nth Binary String
class Solution {
public char findKthBit(int n, int k) {
return (char) ('0' + dfs(n, k));
}
private int dfs(int n, int k) {
if (k == 1) {
return 0;
}
if ((k & (k - 1)) == 0) {
return 1;
}
int m = 1 << n;
if (k * 2 < m - 1) {
return dfs(n - 1, k);
}
return dfs(n - 1, m - k) ^ 1;
}
}
// Accepted solution for LeetCode #1545: Find Kth Bit in Nth Binary String
func findKthBit(n int, k int) byte {
var dfs func(n, k int) int
dfs = func(n, k int) int {
if k == 1 {
return 0
}
if k&(k-1) == 0 {
return 1
}
m := 1 << n
if k*2 < m-1 {
return dfs(n-1, k)
}
return dfs(n-1, m-k) ^ 1
}
return byte('0' + dfs(n, k))
}
# Accepted solution for LeetCode #1545: Find Kth Bit in Nth Binary String
class Solution:
def findKthBit(self, n: int, k: int) -> str:
def dfs(n: int, k: int) -> int:
if k == 1:
return 0
if (k & (k - 1)) == 0:
return 1
m = 1 << n
if k * 2 < m - 1:
return dfs(n - 1, k)
return dfs(n - 1, m - k) ^ 1
return str(dfs(n, k))
// Accepted solution for LeetCode #1545: Find Kth Bit in Nth Binary String
struct Solution;
use std::cmp::Ordering::*;
impl Solution {
fn find_kth_bit(n: i32, k: i32) -> char {
if Self::find(n, k - 1) == 0 {
'0'
} else {
'1'
}
}
fn find(n: i32, k: i32) -> i32 {
if n == 1 {
0
} else {
let size = (1 << n) - 1;
match (size / 2).cmp(&k) {
Equal => 1,
Greater => Self::find(n - 1, k),
Less => 1 - Self::find(n - 1, size - 1 - k),
}
}
}
}
#[test]
fn test() {
let n = 3;
let k = 1;
let res = '0';
assert_eq!(Solution::find_kth_bit(n, k), res);
let n = 4;
let k = 11;
let res = '1';
assert_eq!(Solution::find_kth_bit(n, k), res);
let n = 1;
let k = 1;
let res = '0';
assert_eq!(Solution::find_kth_bit(n, k), res);
let n = 2;
let k = 3;
let res = '1';
assert_eq!(Solution::find_kth_bit(n, k), res);
let n = 3;
let k = 7;
let res = '1';
assert_eq!(Solution::find_kth_bit(n, k), res);
}
// Accepted solution for LeetCode #1545: Find Kth Bit in Nth Binary String
function findKthBit(n: number, k: number): string {
const dfs = (n: number, k: number): number => {
if (k === 1) {
return 0;
}
if ((k & (k - 1)) === 0) {
return 1;
}
const m = 1 << n;
if (k * 2 < m - 1) {
return dfs(n - 1, k);
}
return dfs(n - 1, m - k) ^ 1;
};
return dfs(n, k).toString();
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.