Find Kth Bit in Nth Binary String - Practice Coding Problems

Find Kth Bit in Nth Binary String - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 3, k = 1

› Output: 0

💡 Note: S3 = "0111001". The 1st bit is "0"

Example 2 — Middle Position

$ Input: n = 4, k = 11

› Output: 1

💡 Note: S4 = "011100110110001". The 11th bit is "1"

Example 3 — Second Half

$ Input: n = 2, k = 3

› Output: 1

💡 Note: S2 = "011". The 3rd bit is "1"

Constraints

1 ≤ n ≤ 20
1 ≤ k ≤ 2ⁿ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=3, k=5 - find 5th bit in S3

Pattern

S3 = S2 + "1" + reverse(invert(S2))

Result

Navigate to position 5 without building full string

Key Takeaway

🎯 Key Insight: The recursive structure allows us to find any bit without building exponentially large strings

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is recognizing the recursive structure: each Sn follows the pattern Sn-1 + "1" + reverse(invert(Sn-1)). Instead of building massive strings, we can use this pattern to directly navigate to the kth position. The optimal approach uses recursion to identify which section contains our target and applies position mapping with inversion when needed. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Pattern Recognition	O(n)	O(n)	Use the recursive structure to find the kth bit without building the entire string
Brute Force - Build Complete String	O(2ⁿ)	O(2ⁿ)	Build the entire Sn string step by step, then return the kth character

Recursive Pattern Recognition — Algorithm Steps

Calculate the length of Sn as 2^n - 1
Find the middle position (length/2 + 1)
If k is at middle, return '1'
If k is in first half, recursively search Si-1
If k is in second half, find corresponding position in Si-1 and invert the result

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Structure

Sn = Sn-1 + '1' + reverse(invert(Sn-1))

Find Position

Determine if k is in first half, middle, or second half

Recurse or Return

Either return '1' for middle, or recurse with position mapping

Code -

solution.c — C

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

char findKthBit(int n, int k) {
    if (n == 1) {
        return '0';
    }
    
    int length = (1 << n) - 1;  // 2^n - 1
    int mid = length / 2 + 1;
    
    if (k == mid) {
        return '1';
    } else if (k < mid) {
        return findKthBit(n - 1, k);
    } else {
        // k is in the second half
        int correspondingPos = length - k + 1;
        char bit = findKthBit(n - 1, correspondingPos);
        return bit == '0' ? '1' : '0';  // invert
    }
}

char* solution(int n, int k) {
    char* result = malloc(2);
    result[0] = findKthBit(n, k);
    result[1] = '\0';
    return result;
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    char* result = solution(n, k);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

At most n recursive calls, each doing O(1) work

✓ Linear Growth

Space Complexity

O(n)

Recursion call stack depth is at most n

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Pattern Recognition — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler