LeetCode 1545 | Find Kth Bit in Nth Binary String | Java | Medium | Recursion | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 1545 — Find Kth Bit in Nth Binary String using Divide and Conquer in Java.
We are given two positive integers n and k. The binary string Sn is generated recursively by combining the previous string, a central one, and the reversed and inverted version of the previous string.
Instead of generating these exponentially growing strings, which can contain more than one million characters, we use their mathematical symmetry to find the kth bit directly.
Our solution uses an iterative Divide and Conquer approach with cumulative bit inversion tracking. At each step, we calculate the center position. If k matches the center, we determine the answer immediately. If k is in the left half, it maps directly to the previous string. If k is in the right half, we reflect its position using two raised to n minus k and flip the bit.
This approach avoids generating strings and eliminates unnecessary memory allocations. It achieves O(n) time complexity and O(1) auxiliary space, finishing in fewer than 20 iterations.
🔥 Problem Highlights
✅ Analyzed string symmetry using left half, center bit, and right half
✅ Reflected right-half positions using the symmetry property
✅ Tracked bit inversions without creating additional strings
✅ Applied early return when the center position is reached
✅ Used an iterative approach without recursion stack overhead
✅ Achieved O(n) time complexity and O(1) auxiliary space
⏱️ TIMESTAMPS
00:00 Intro & Daily Challenge Overview
01:16 Problem Understanding & String Growth Rules
03:15 Key Observation: Symmetrical Reduction & Center Bit
05:06 Logarithmic Divide & Conquer Strategy (4 Steps)
06:41 Clean Java Solution Walkthrough Line by Line
08:00 Test Cases Walkthrough & Step-by-Step Simulation
09:43 Time Complexity Analysis (O(N) Time - 0 ms)
10:36 Space Complexity Analysis (O(1) Space)
11:18 Outro & Resources
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/March/3-March/1545-Find-Kth-Bit-in-Nth-Binary-String
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/3-March/1545-Find-Kth-Bit-in-Nth-Binary-String/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/3-March/1545-Find-Kth-Bit-in-Nth-Binary-String/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/3-March/1545-Find-Kth-Bit-in-Nth-Binary-String/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/3-March/1545-Find-Kth-Bit-in-Nth-Binary-String/solution.js
🔗 LeetCode Source Code
📌 Add the link here
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Divide and Conquer
Recursion Patterns
Binary String Manipulation
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
When k is in the right half of Sn, which position does it map to in the previous string?
1️⃣ Two raised to the power n, minus k
2️⃣ k minus the center position
3️⃣ The center position minus k
4️⃣ Half of k plus one
#LeetCode1545 #LeetCode #FindKthBitInNthBinaryString #Java #JavaDSA #DivideAndConquer #Recursion #String #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 1545 — Find Kth Bit in Nth Binary String using Divide and Conquer in Java.
We are given two positive integers n and k. The binary string Sn is generated recursively by combining the previous string, a central one, and the reversed and inverted version of the previous string.
Instead of generating these exponentially growing strings, which can contain more than one million characters, we use their mathematical symmetry to find the kth bit directly.
Our solution uses an iterative Divide and Conquer approach with cumulative bit inversion tracking. At each step, we calculate the center position. If k matches the center, we determine the answer immediately. If k is in the left half, it maps directly to the previous string. If k is in the right half, we reflect its position using two raised to n minus k and flip the bit.
This approach avoids generating strings and eliminates unnecessary memory allocations. It achieves O(n) time complexity and O(1) auxiliary space, finishing in fewer than 20 iterations.
🔥 Problem Highlights
✅ Analyzed string symmetry using left half, center bit, and right half
✅ Reflected right-half positions using the symmetry property
✅ Tracked bit inversions without creating additional strings
✅ Applied early return when the center position is reached
✅ Used an iterative approach without recursion stack overhead
✅ Achieved O(n) time complexity and O(1) auxiliary space
⏱️ TIMESTAMPS
00:00 Intro & Daily Challenge Overview
01:16 Problem Understanding & String Growth Rules
03:15 Key Observation: Symmetrical Reduction & Center Bit
05:06 Logarithmic Divide & Conquer Strategy (4 Steps)
06:41 Clean Java Solution Walkthrough Line by Line
08:00 Test Cases Walkthrough & Step-by-Step Simulation
09:43 Time Complexity Analysis (O(N) Time - 0 ms)
10:36 Space Complexity Analysis (O(1) Space)
11:18 Outro & Resources
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/March/3-March/1545-Find-Kth-Bit-in-Nth-Binary-String
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/3-March/1545-Find-Kth-Bit-in-Nth-Binary-String/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/3-March/1545-Find-Kth-Bit-in-Nth-Binary-String/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/3-March/1545-Find-Kth-Bit-in-Nth-Binary-String/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/3-March/1545-Find-Kth-Bit-in-Nth-Binary-String/solution.js
🔗 LeetCode Source Code
📌 Add the link here
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Divide and Conquer
Recursion Patterns
Binary String Manipulation
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
When k is in the right half of Sn, which position does it map to in the previous string?
1️⃣ Two raised to the power n, minus k
2️⃣ k minus the center position
3️⃣ The center position minus k
4️⃣ Half of k plus one
#LeetCode1545 #LeetCode #FindKthBitInNthBinaryString #Java #JavaDSA #DivideAndConquer #Recursion #String #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
