1545. Find Kth Bit in Nth Binary String - Solution

Q: Is Find Kth Bit in Nth Binary String easy or hard?

The problem is rated Medium because the brute-force simulation is straightforward but inefficient, while the optimal solution requires recognizing a recursive symmetry in the string definition. Once the midpoint and mirror relationship are identified, the implementation becomes concise.

Q: Find Kth Bit in Nth Binary String Python/Java solution

Both Python and Java implementations typically follow the recursive approach. The function checks the middle index of the current length (2^n − 1), decides whether k lies in the left or right half, and applies inversion when mapping from the right side. The recursion depth is at most n.

Q: How to solve Find Kth Bit in Nth Binary String in O(n)?

Use the recursive symmetry of the string. Compute the total length (2^n − 1) and identify the middle position. If k equals the middle, the answer is '1'. If k is on the left, recurse on (n-1, k). If k is on the right, map to the mirrored index (length − k + 1), recurse, and invert the result. This reduces the problem size at every step.

Q: What is the best approach for Find Kth Bit in Nth Binary String?

The recursive mathematical approach is the most efficient. Instead of constructing the full string of length 2^n − 1, it uses the observation that the middle bit is always '1' and the right half is the reversed inverted version of the left half. By mapping positions recursively, the problem is solved in O(n) time with O(n) recursion space.

Q: Is Find Kth Bit in Nth Binary String asked at Google/Amazon/Meta?

Variants of recursive pattern and symmetry problems appear in interviews at large tech companies including Amazon, Google, and Meta. The question tests recursion, pattern recognition, and the ability to avoid brute-force construction of exponentially growing structures.

Q: What data structure is used in Find Kth Bit in Nth Binary String?

The brute-force method uses basic string manipulation to build the sequence. The optimal solution relies mainly on recursion and mathematical reasoning rather than storing the entire string, making it more space efficient.

Q: What is the time complexity of Find Kth Bit in Nth Binary String?

The optimal recursive solution runs in O(n) time because each recursive step reduces the problem from n to n-1 while recalculating the position. The brute-force simulation approach takes O(2^n) time and space since the full binary string must be constructed.

The problem

Given two positive integers n and k, the binary string S_n is formed as follows:

S₁ = "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 the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first four strings in the above sequence are:

S₁= "0"
S₂= "011"
S₃= "0111001"
S₄ = "011100110110001"

Return the k^th bit in S_n. It is guaranteed that k is valid for the given n.

Example 1:

Input: n = 3, k = 1
Output: "0"
Explanation: S₃ is "0111001".
The 1^st bit is "0".

Example 2:

Input: n = 4, k = 11
Output: "1"
Explanation: S₄ is "011100110110001".
The 11^th bit is "1".

Constraints:

1 <= n <= 20
1 <= k <= 2ⁿ - 1

Approach overview

Problem Overview: The binary string S_n is built recursively. S_1 = "0". For every next step: S_n = S_{n-1} + "1" + reverse(invert(S_{n-1})). The task is to return the kth bit (1-indexed) in S_n without necessarily constructing the entire string.

Approach 1: Iterative Construction (O(2^n) time, O(2^n) space)

This method directly simulates the definition of the sequence. Start from S_1 = "0". For each step, generate the next string by appending "1" and then the reversed inverted version of the current string. Inversion flips every bit (0 → 1, 1 → 0) and reversing changes the order. Once the string for n is built, return the character at index k - 1. The approach uses basic string operations and straightforward simulation. The downside is exponential growth: the string length becomes 2^n - 1, which quickly becomes impractical for larger n.

Approach 2: Recursive Mathematical Insight (O(n) time, O(n) space)

The recursive structure of the string reveals a pattern that avoids building it. The total length of S_n is 2^n - 1, and the middle element is always '1'. If k equals the middle index, the answer is immediately '1'. If k is in the left half, the problem reduces to finding the kth bit of S_{n-1}. If k lies in the right half, map it to the mirrored position in the left half using k' = length - k + 1, then invert the result. This works because the right half is exactly reverse(invert(S_{n-1})). The recursion depth is at most n, so the time complexity becomes O(n) with O(n) stack space. This technique leverages properties of recursion and symmetry in the string construction.

Recommended for interviews: Interviewers typically expect the recursive mathematical approach. The brute-force construction shows you understand how the sequence is generated, but recognizing the symmetry and middle pivot demonstrates stronger problem-solving skills. The optimal approach reduces exponential work to a simple recursive reduction based on position.

Approach 1: Iterative Construction

This approach involves directly simulating the sequence construction up to the desired nth binary string and retrieving the k-th bit from it. Since the problem ensures n and k are constrained, this method remains efficient enough.

Python

def invertChar(c):
    return '1' if c == '0' else '0'

def invertAndReverse(s):
    return ''.join(invertChar(c) for c in s)[::-1]

def findKthBit(n, k):
    S = "0"
    for i in range(2, n + 1):
        S = S + "1" + invertAndReverse(S)
    return S[k - 1]

n = 4
k = 11
print("Output:", findKthBit(n, k))

Java

public class Solution {
    public static char invertChar(char c) {
        return c == '0' ? '1' : '0';
    }

    public static String invertAndReverse(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--) {
            sb.append(invertChar(s.charAt(i)));
        }
        return sb.toString();
    }

    public static char findKthBit(int n, int k) {
        String S = "0";
        for (int i = 2; i <= n; i++) {
            S = S + "1" + invertAndReverse(S);
        }
        return S.charAt(k - 1);
    }

    public static void main(String[] args) {
        int n = 4, k = 11;
        System.out.println("Output: " + findKthBit(n, k));
    }
}

C++

#include <iostream>
#include <string>

char invertChar(char c) {
    return c == '0' ? '1' : '0';
}

std::string invertAndReverse(const std::string& str) {
    std::string inverted = str;
    for (char& c : inverted) {
        c = invertChar(c);
    }
    std::reverse(inverted.begin(), inverted.end());
    return inverted;
}

char findKthBit(int n, int k) {
    std::string S = "0";
    for (int i = 2; i <= n; i++) {
        S = S + "1" + invertAndReverse(S);
    }
    return S[k - 1];
}

int main() {
    int n = 4, k = 11;
    std::cout << "Output: " << findKthBit(n, k) << std::endl;
    return 0;
}

JavaScript

function invertChar(c) {
    return c === '0' ? '1' : '0';
}

function invertAndReverse(s) {
    return s.split('').map(invertChar).reverse().join('');
}

function findKthBit(n, k) {
    let S = "0";
    for (let i = 2; i <= n; i++) {
        S = S + '1' + invertAndReverse(S);
    }
    return S[k - 1];
}

const n = 4;
const k = 11;
console.log(`Output: ${findKthBit(n, k)}`);

#include <stdio.h>
#include <string.h>

char invertChar(char c) {
    return c == '0' ? '1' : '0';
}

void reverseString(char* str, int n) {
    for (int i = 0; i < n / 2; i++) {
        char temp = str[i];
        str[i] = str[n - i - 1];
        str[n - i - 1] = temp;
    }
}

void invertString(char* str, int n) {
    for (int i = 0; i < n; i++) {
        str[i] = invertChar(str[i]);
    }
}

char findKthBit(int n, int k) {
    char S[1048576] = "0"; // S_n max length is 2^20 - 1
    int currentLength = 1;

    for (int i = 2; i <= n; i++) {
        int len = currentLength;
        S[len] = '1';

        for (int j = 0; j < len; j++) {
            S[len + 1 + j] = invertChar(S[len - 1 - j]);
        }

        currentLength = 2 * len + 1;
    }

    return S[k - 1];
}

int main() {
    int n = 4, k = 11;
    printf("Output: %c\n", findKthBit(n, k));
    return 0;
}

using System;
using System.Text;

public class Solution {
    public static char InvertChar(char c) {
        return c == '0' ? '1' : '0';
    }

    public static string InvertAndReverse(string s) {
        char[] chars = new char[s.Length];
        for (int i = 0; i < s.Length; i++) {
            chars[i] = InvertChar(s[s.Length - i - 1]);
        }
        return new string(chars);
    }

    public static char FindKthBit(int n, int k) {
        string S = "0";
        for (int i = 2; i <= n; i++) {
            S = S + "1" + InvertAndReverse(S);
        }
        return S[k - 1];
    }

    public static void Main() {
        int n = 4, k = 11;
        Console.WriteLine("Output: " + FindKthBit(n, k));
    }
}

The Python solution iteratively builds the binary string by continually appending the transformed version of the previously constructed string. The transformation involves reversing and inverting the bits following the pattern given in the problem definition.

Complexity

Time Complexity: O(2^n), as iteratively forming the sequence.
Space Complexity: O(2^n), maintaining storage for the full sequence.

Try this approach in the editor

Approach 2: Recursive Mathematical Approach

This approach leverages the recursive nature and mathematical properties of the sequence to find the k-th bit without constructing the entire string. By recognizing the symmetry and structure, we use recursive calculations to directly determine the desired bit.

Python

def findKthBitRecursively(n, k):
    if n == 1:
        return '0'
    length = (1 << n) - 1  # Length of S_n
    mid = (length + 1) // 2
    if k == mid:
        return '1'
    if k < mid:
        return findKthBitRecursively(n - 1, k)
    else:
        return '1' if findKthBitRecursively(n - 1, length - k + 1) == '0' else '0'

n = 4
k = 11
print("Output:", findKthBitRecursively(n, k))

Java

public class SolutionRecursive {
    public static char findKthBitRecursively(int n, int k) {
        if (n == 1) return '0';
        int length = (1 << n) - 1; // Length of S_n
        int mid = (length + 1) / 2;
        if (k == mid) return '1';
        if (k < mid) return findKthBitRecursively(n - 1, k);
        else {
            char bit = findKthBitRecursively(n - 1, length - k + 1);
            return bit == '0' ? '1' : '0';
        }
    }

    public static void main(String[] args) {
        int n = 4, k = 11;
        System.out.println("Output: " + findKthBitRecursively(n, k));
    }
}

C++

#include <iostream>

char findKthBitRecursively(int n, int k) {
    if (n == 1) return '0';
    int length = (1 << n) - 1; // Length of S_n
    int mid = (length + 1) / 2;
    if (k == mid) return '1';
    if (k < mid) return findKthBitRecursively(n - 1, k);
    else {
        char bit = findKthBitRecursively(n - 1, length - k + 1);
        return bit == '0' ? '1' : '0';
    }
}

int main() {
    int n = 4, k = 11;
    std::cout << "Output: " << findKthBitRecursively(n, k) << std::endl;
    return 0;
}

JavaScript

function findKthBitRecursively(n, k) {
    if (n === 1) return '0';
    const length = (1 << n) - 1; // Length of S_n
    const mid = (length + 1) / 2;
    if (k === mid) return '1';
    if (k < mid) return findKthBitRecursively(n - 1, k);
    else {
        return findKthBitRecursively(n - 1, length - k + 1) === '0' ? '1' : '0';
    }
}

const n = 4;
const k = 11;
console.log(`Output: ${findKthBitRecursively(n, k)}`);

#include <stdio.h>

char findKthBitRecursively(int n, int k) {
    if (n == 1) return '0';
    int length = (1 << n) - 1; // Length of S_n
    int mid = (length + 1) / 2;
    if (k == mid) return '1';
    if (k < mid) return findKthBitRecursively(n - 1, k);
    else {
        char bit = findKthBitRecursively(n - 1, length - k + 1);
        return bit == '0' ? '1' : '0';
    }
}

int main() {
    int n = 4, k = 11;
    printf("Output: %c\n", findKthBitRecursively(n, k));
    return 0;
}

using System;

public class SolutionRecursive {
    public static char FindKthBitRecursively(int n, int k) {
        if (n == 1) return '0';
        int length = (1 << n) - 1; // S_n length
        int mid = (length + 1) / 2;
        if (k == mid) return '1';
        if (k < mid) return FindKthBitRecursively(n - 1, k);
        else {
            return FindKthBitRecursively(n - 1, length - k + 1) == '0' ? '1' : '0';
        }
    }

    public static void Main() {
        int n = 4, k = 11;
        Console.WriteLine("Output: " + FindKthBitRecursively(n, k));
    }
}

This Python solution purely uses recursion to determine when a desired bit falls based on cycle splitting and transformations. Repeatedly computes the k-bit recursively by centering decisions around middle positions effectively.

Complexity

Time Complexity: O(n), driven by linear recursive pattern.
Space Complexity: O(n), due to recursive call depth.

Try this approach in the editor

Approach 3: Case Analysis + Recursion

We can observe that for S_n, the first half is the same as S_{n-1}, and the second half is the reverse and negation of S_{n-1}. Therefore, we can design a function dfs(n, k), which represents the k-th character of the n-th string. The answer is dfs(n, k).

The calculation process of the function dfs(n, k) is as follows:

If k = 1, then the answer is 0;
If k is a power of 2, then the answer is 1;
If k times 2 < 2^n - 1, it means that k is in the first half, and the answer is dfs(n - 1, k);
Otherwise, the answer is dfs(n - 1, 2^n - k) \oplus 1, where \oplus represents the XOR operation.

The time complexity is O(n), and the space complexity is O(n). Here, n is the given n in the problem.

TypeScript

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();
}

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))
}

Rust

impl Solution {
    pub fn find_kth_bit(n: i32, k: i32) -> char {
        fn dfs(n: i32, k: i32) -> i32 {
            if k == 1 {
                return 0;
            }
            if (k & (k - 1)) == 0 {
                return 1;
            }
            let m: i32 = 1 << n;
            if k * 2 < m - 1 {
                dfs(n - 1, k)
            } else {
                dfs(n - 1, m - k) ^ 1
            }
        }

        if dfs(n, k) == 0 { '0' } else { '1' }
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Iterative Construction	Time Complexity: O(2^n), as iteratively forming the sequence. Space Complexity: O(2^n), maintaining storage for the full sequence.
Recursive Mathematical Approach	Time Complexity: O(n), driven by linear recursive pattern. Space Complexity: O(n), due to recursive call depth.
Case Analysis + Recursion	–

Complexity analysis

Approach	Time	Space	When to Use
Iterative Construction	O(2^n)	O(2^n)	Good for understanding the definition and for very small n where full simulation is feasible.
Recursive Mathematical Approach	O(n)	O(n)	Best choice for interviews and large n. Avoids constructing the full string using symmetry and recursion.

Frequently asked questions

Is Find Kth Bit in Nth Binary String easy or hard?

The problem is rated Medium because the brute-force simulation is straightforward but inefficient, while the optimal solution requires recognizing a recursive symmetry in the string definition. Once the midpoint and mirror relationship are identified, the implementation becomes concise.

Find Kth Bit in Nth Binary String Python/Java solution

Both Python and Java implementations typically follow the recursive approach. The function checks the middle index of the current length (2^n − 1), decides whether k lies in the left or right half, and applies inversion when mapping from the right side. The recursion depth is at most n.

How to solve Find Kth Bit in Nth Binary String in O(n)?

Use the recursive symmetry of the string. Compute the total length (2^n − 1) and identify the middle position. If k equals the middle, the answer is '1'. If k is on the left, recurse on (n-1, k). If k is on the right, map to the mirrored index (length − k + 1), recurse, and invert the result. This reduces the problem size at every step.

What is the best approach for Find Kth Bit in Nth Binary String?

The recursive mathematical approach is the most efficient. Instead of constructing the full string of length 2^n − 1, it uses the observation that the middle bit is always '1' and the right half is the reversed inverted version of the left half. By mapping positions recursively, the problem is solved in O(n) time with O(n) recursion space.

Is Find Kth Bit in Nth Binary String asked at Google/Amazon/Meta?

Variants of recursive pattern and symmetry problems appear in interviews at large tech companies including Amazon, Google, and Meta. The question tests recursion, pattern recognition, and the ability to avoid brute-force construction of exponentially growing structures.

What data structure is used in Find Kth Bit in Nth Binary String?

The brute-force method uses basic string manipulation to build the sequence. The optimal solution relies mainly on recursion and mathematical reasoning rather than storing the entire string, making it more space efficient.

What is the time complexity of Find Kth Bit in Nth Binary String?

The optimal recursive solution runs in O(n) time because each recursive step reduces the problem from n to n-1 while recalculating the position. The brute-force simulation approach takes O(2^n) time and space since the full binary string must be constructed.

Find Kth Bit in Nth Binary String solution and explanation

The problem

Approach overview

Approach 1: Iterative Construction

Approach 2: Recursive Mathematical Approach

Approach 3: Case Analysis + Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Kth Bit in Nth Binary String solution and explanation

The problem

Approach overview

Approach 1: Iterative Construction

Approach 2: Recursive Mathematical Approach

Approach 3: Case Analysis + Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems