Find Kth Bit In Nth Binary String · Interview Problem

Back to problems

Leetcode

Medium

Strings

Recursion

Bit Manipulation

Google

Find Kth Bit In Nth Binary String

Find the $k$ -th bit in a recursively defined binary string of length $2^n-1$ .

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Find K-th Bit in N-th Binary String

gfg

Problem Statement

Problem

You are given two integers $n$ and $k$ .

Define a binary string $S_n$ recursively as follows:

$S_1 = "0"$
For $n > 1$ , construct $S_n$ by taking $S_{n-1}$ , appending a 0, then appending the reverse of $S_{n-1}$ with every bit flipped (0 becomes 1, and 1 becomes 0).

Your task is to return the $k$ -th character of $S_n$ using 1-based indexing.

This problem is designed to test your ability to reason about recursive structure without explicitly building the full string.

Input Format

Two integers $n$ and $k$ .
$n$ is the recursion level.
$k$ is the 1-based position to query in $S_n$ .

Output Format

Return the character at position $k$ in $S_n$ .
The answer is either 0 or 1.

Constraints

$1 \le n$
$1 \le k \le 2^n - 1$
The intended solution should avoid constructing the full string for large $n$ .

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 3, k = 1

Output

Explanation

$S_3 = 0111001$ , so the first bit is 0.

Example 2

Input

n = 3, k = 5

Output

Explanation

$S_3 = 0111001$ , and the 5th bit is the middle bit 0.

Show 1 more example

Example 3

Input

n = 4, k = 11

Output

Explanation

The recursive string $S_4$ has length $15$. Tracing the position through mirrored halves gives bit 1 at index 11.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress