Find Kth Bit in Nth Binary String | Detailed Recursion | Dry Run | Leetcode 1545 | codestorywithMIK

This is the 9th Video of our Playlist "Recursion : Popular Interview Problems" by codestorywithMIK

Similar Problems -

In this video we will try to solve a good Recursion problem : Find Kth Bit in Nth Binary String | Detailed Recursion | Detailed Dry Run | Leetcode 1545 | codestorywithMIK

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Find Kth Bit in Nth Binary String | Detailed Recursion | Detailed Dry Run | Leetcode 1545 | codestorywithMIK
Company Tags : will update later

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Summary :
The approach for solving the problem of finding the k-th bit in the n-th binary sequence follows these steps:

Recursive Structure: The binary sequence at level n is built recursively by taking the sequence at level n-1, adding a '1', and then appending the reverse of n-1 where each bit is flipped. This pattern can be leveraged to recursively find the k-th bit.

Base Case: When n = 1, the sequence is just '0', so if the search reaches this level, the result is '0'.

Midpoint Check: The sequence length at level n is 2^n - 1. The midpoint is always '1'. If k is exactly at this midpoint, return '1'.

First Half: If k lies in the first half of the sequence, the answer can be found by recursively searching the corresponding position in the sequence for n-1.

Second Half: If k is in the second half, it corresponds to a mirrored and flipped bit of the first half. Recursively find the corresponding bit in the first half and flip it.

This approach efficiently uses recursion to handle the reverse and flip operations without generating the entire sequence explicitly.

✨ Timelines✨
00:00 - Introduction

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[jeehub]

Solution toh sab batate ha par jo thought process hona chahiye optimal solution tak jaane ka ye toh bhaiya se hi sikha ha❤❤

[rahulharsh]

Sir my main reason to resume dsa and deep dive into it is you at first i thought its a very long process but the thought process that show in all of your videos just make me curious and happy

[UmmeKNeha]

I am waiting for your video every day. Thank you for the detailed video. keep doing. also a request, please try to upload as early as possible.

[nee-]

thank you bhaiya for the amazing content ...i hope i will improve and learn everyday day i will get a good placement

[ManishKumar-kwqe]

was able to solve it. because you have taught this pattern very well in previous two questions.
Thanks bro 🫡🫡❤❤

[ugcwithaddi]

Was waiting.
It’s same as Leetcode-3307

[SkAkibuzzamanJony]

Thank you bhaiya for these awesome detailed videos every day 😇
Can you please make a video on this problem : 1632. Rank Transform of a Matrix

[dipalisharma]

Tqsm for the vedio bhaiya avi apke relative kise h..hope ki achi health hongi unki❤❤

[jeehub]

Bhaiya isme else wale me aise bhi likh sakte ha ki solve function call kia jo bhi output aaya uska XOR le lia 1 se apne aap flip ho jayga ❤❤

[LittleLearnersStories-ly]

Bhaiya i solved this question on my own but i used a diiferent function and created a string due to which there is some space complexity. But this approach didnt even touch my head

[tomiokascuteness]

Iterative Divide and Conquer Approach pe bhi video banado

[VanshGupta]

my approach :
class Solution {

private:
string mani(string t){
for(auto &c : t){
if(c == '0') c = '1';
else c = '0';
}
reverse(t.begin(), t.end());
return t;
}

string Solve(int n, vector<string>&dp){
if(n == 1) return "0";
if(dp[n] != "-1") return dp[n];
return dp[n] = Solve(n-1, dp) + "1" + mani(Solve(n-1, dp));
}

public:
char findKthBit(int n, int k) {
vector<string>dp(n+1, "-1");
string ans = Solve(n, dp);
return ans[k-1];
}
};

[rahilkhera]

Hi MIK, Can you please explain the fourth approach mentioned in the editorial, which is solving this using bit manipulation? I read it a few times and understood the solution but failed to understand its thought process. It would be a great help if you can make a video on that. Btw thanks for the great work.

[varunaggarwal]

class Solution {
public:
char findKthBit(int n, int k) {
if (n == 1) { // Base case: the first string is "0"
return '0';
}

// Calculate the length of Sn
int length = (1 << n) - 1; // Length of Sn is 2^n - 1

int mid = length / 2 + 1; // Middle position

if (k == mid) {
return '1'; // The middle character is always '1'
}

if (k < mid) {
return findKthBit(n - 1, k); // Before the middle, it's just Sn-1
} else {
// After the middle, it's the inverted and reversed Sn-1
return findKthBit(n - 1, length - k + 1) == '0' ? '1' : '0';
}
}
};

[Abhi-znup]

Sir can you please upload today's lettcode contest solution 2, 3
I know you are busy but please try to upload because upsolving is much important and it is very needed to grow knowledge rapidly 🙏🙏

[aizadiqbal]

can u explain like when we do -1 ?
without observation,
meaning
like kth bit from start, would be same as length - (k-1)

I always get confused in this

[ishaanshandilya]

Bhaiya, what are the chances of getting placed now (7th sem)? given that i come from a 3rd tier university?

[SoumyaPaul-qp]

Bhiya mene to for loop se kr diye O(n) who accept ho gaya

[jeehub]

My Brute force code also got ACCEPTED in this one:👇

char findKthBit(int n, int k) {

if(n==1) return '0';
string str="0";
n=n-1;
while(n--)
{
string temp=str;
reverse(temp.begin(), temp.end());

for(int i=0; i<temp.size(); i++)
{
if(temp[i]=='0')
{
temp[i]='1';
}
else temp[i]='0';
}

str= str+"1"+ temp;

}

return str[k-1];


}

[gui-codes]

Sir aapka ye video dekha tha "Find the K-th Character in String Game II" and ye easily solve karliya. Thoda hint liya tha but hogaya khud se.
Thank you so much for improving me