LeetCode 1545 – Find Kth Bit in Nth Binary String

In this article, we will break down LeetCode 1545: Find Kth Bit in Nth Binary String in a simple and intuitive way. We will go through:

• Problem explanation in simple terms
• Example walkthrough
• Intuition behind the optimized recursive approach
• Java implementation
• Alternative approaches
• Interview tips

---

🔎 Problem Statement

We define a binary string recursively:

S1 = "0"

For n > 1:
Sn = S(n-1) + "1" + reverse(invert(S(n-1)))

Where:

• reverse → reverses the string
• invert → changes 0 → 1 and 1 → 0

You are given two integers n and k. Return the kth bit (1-indexed) of Sn.

In simple words: Build the recursive binary string conceptually and return the kth character.

---

📊 Understanding the Pattern

Step 1: Build Small Strings

S1

0

S2

0 + 1 + 1
= 011

S3

S2 = 011
invert = 100
reverse = 001

S3 = 011 + 1 + 001
= 0111001

S4

0111001 + 1 + 0110001

---

Length Pattern

S1 = 1
S2 = 3
S3 = 7
S4 = 15

Length of Sn = 2ⁿ − 1

---

Structure Pattern

LEFT        MID        RIGHT
S(n-1)       1      reverse(invert(S(n-1)))

• The middle element is always 1
• The right half is mirrored and inverted

This symmetry is the key to solving the problem efficiently.

---

📍 Step-by-Step Example

Input: n = 4, k = 11

Length = 15
Mid = 8

Since 11 > 8, the kth bit lies in the right half.

Mirror index:

mirror = 15 - 11 + 1 = 5

Now solve find(3, 5)

Length = 7
Mid = 4

5 > 4 → Right side again

mirror = 7 - 5 + 1 = 3

Now solve find(2, 3)

Length = 3
Mid = 2

3 > 2 → Right side

mirror = 3 - 3 + 1 = 1

Now solve find(1, 1)

S1 = 0

Backtracking with inversion:

0 → 1 → 0 → 1

Final Answer = 1

---

💡 Intuition Behind the Optimized Approach

Generating the full string would require exponential memory. Instead, observe:

• If k == middle → answer is 1
• If k < middle → problem reduces to (n-1, k)
• If k > middle → mirror index and invert result

This is a classic divide and conquer using symmetry.

Time Complexity: O(n)

Space Complexity: O(n) (recursion stack)

---

💻 Java Implementation

class Solution {
    public char findKthBit(int n, int k) {
        if (n == 1) return '0';
        
        int len = (1 << n) - 1;
        int mid = (len + 1) / 2;
        
        if (k == mid) return '1';
        
        if (k < mid) {
            return findKthBit(n - 1, k);
        } else {
            int mirror = len - k + 1;
            char bit = findKthBit(n - 1, mirror);
            return bit == '0' ? '1' : '0';
        }
    }
}

---

⚡ Alternative Approaches

1️⃣ Brute Force String Construction

Construct the entire string until Sn.

• ✔ Easy to understand
• ❌ Exponential memory usage

2️⃣ Iterative Without Recursion

Simulate the recursion using a loop and track inversion count.

• ✔ Avoids recursion stack
• ❌ Slightly harder to reason about

3️⃣ Binary Tree Perspective

View the string as a symmetric binary tree structure.

• ✔ Deep conceptual clarity
• ❌ Overkill for simple interviews

---

🎯 Interview Strategy

• Start by explaining the recursive definition clearly.
• Identify the middle element pattern.
• Explain mirror index logic carefully.
• Highlight divide-and-conquer reasoning.

Whenever you see:

S(n) = S(n-1) + something + transform(S(n-1))

Think immediately: Mirror Index + Inversion Trick.

---

📌 Conclusion

LeetCode 1545 is not a string-building problem. It is a recursion and symmetry problem.

Once you recognize the structural pattern, the solution becomes clean and elegant.

Master this pattern, and many recursive interview problems will become much easier.

---

Related Topics: Recursion, Divide and Conquer, Binary Strings, Pattern Recognition, Interview Preparation