1545. Find Kth Bit in Nth Binary String | Leetcode Daily Challenge | DSA | Java | FAANG

Problem Name:
1545. Find Kth Bit in Nth Binary String

Problem Statement:
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.

Problem Link:

Solution Link:

Graph Playlist:

Java Plus DSA Placement Course Playlist:

Java Plus DSA Sheet:

Notes:

Telegram Link:

Ultimate Recursion Series Playlist:

Samsung Interview Experience:

Company Tags:
Facebook | Amazon | Microsoft | Netflix | Google | LinkedIn | Pega Systems | VMware | Adobe | Samsung

Timestamp:
0:00 - Introduction

#ShashwatTiwari #coding​​ #problemsolving​

[shashwat_tiwari_st]

Like target is 150! Please do like if you have understood the explanation as well as the code!

[opkrchauhan_]

class Solution {
public char findKthBit(int n, int k) {
String str = getString(n);
char ch=str.charAt(0);
for(int i=0;i<str.length();i++){
if((i+1)==k){
ch = str.charAt(i);
}
}
return ch;
}

public String getString(int n){
if(n==1){
return "0";
}
String previous= getString(n-1);
String next = new
return previous +"1"+next;

}
public String Invert(String s){
char []ch = s.toCharArray();
for(int i=0;i<s.length();i++){
if(ch[i]=='0'){
ch[i]='1';
}
if(ch[i]=='1'){
ch[i]='0';
}
}
String str="";
for(char c : ch){
str = c + str;
}
return str;
}
} Note Working

[rudrakshgupta]

CPP Solution
class Solution {
public:
char fn(int len, int k){
if(len==1){
return '0';
}
int half=len/2;
int middle=half+1;
if(k==middle){
return '1';
}else if(k<middle){
return fn(half, k);
}else{
char ans=fn(half, 1+len-k);
return ans=='0' ? '1': '0';
}
}
char findKthBit(int n, int k) {
int len=pow(2, n)-1;
return fn(len, k);
}
};

[dayashankarlakhotia]

public int find KthBit(int n, int k){
int cnt=0, len=(int)Math.pow(2, n)-1;
while(k>1){
if(k==len/2+1){
return cnt%2==0?'1':'0';
}
if(k>len/2){
k=len+1-k;
cnt++;
}
len/=2;
}
return cnt%2==0?'0':'1';
}
Iterater apporach 🎉❤