Skip to main content
Talentd

Find Kth Bit in Nth Binary String - Solution & Explanation

MediumStringRecursionSimulation20 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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.

 

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 <= 20
  • 1 <= k <= 2n - 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.

The solution constructs each sequence iteratively using the relationship: Si = Si-1 + '1' + reverse(invert(Si-1)). We manage a buffer array S that stores each sequence step-by-step until Sn is reached, whereupon we simply return the k-th position.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n), as each step fully constructs the sequence of size approximately 2^n.
Space Complexity: O(2^n), owing to storing 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.

The recursive approach utilizes the breakdown of the sequence into its two halves with a central break. We trace the k-th bit's location through recursion: if it's in the right half, consider the transformed position in the left. This efficient strategy provides a path to directly compute the k-th bit without constructing full strings.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), limited by the recursion depth of n.
Space Complexity: O(n), due to recursive call stack.

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.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Construction

Time Complexity: O(2^n), as each step fully constructs the sequence of size approximately 2^n.
Space Complexity: O(2^n), owing to storing the full sequence.

Recursive Mathematical Approach

Time Complexity: O(n), limited by the recursion depth of n.
Space Complexity: O(n), due to recursive call stack.

Case Analysis + Recursion—

Detailed Complexity Analysis

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

Video Solution

Find Kth Bit in Nth Binary String | Detailed Recursion | Dry Run | Leetcode 1545 | codestorywithMIK • codestorywithMIK • 14,471 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find Kth Bit in Nth Binary String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring