Kth Symbol in Grammar
ฝัง
- เผยแพร่เมื่อ 20 ต.ค. 2024
- Problem Description: leetcode.com/p...
On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.
Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).
The Notes that I taught in the video and the Working Code (if any) will be available on my Patreon page under the "Notes, Code And Support" tier.
Link: / adityaverma
Video Pdf Notes: / 38704577 .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
Before watching this video:
I wasted first 30 minutes trying to solve it using loop
=>RESULT - Got TLE
I wasted next 15 minutes trying to solve it using IBH method learned in previous videos
=>RESULT - Got TLE again in the same test case, but i was proud of myself that i was able to code it using IBH method so easily.
Then i watched this video till 9:32 and then paused and then kept trying for next 45 minutes trying to observe any pattern and code it using IBH.
=>RESULT - Accepted
The level of understanding this man has given me in recursion is just exceptional. Thanks to one of my college senior bhaiya who recommended me this channel. He just told me that there is no other youtube channel that has taught recursion so much easily as taught by aditya verma.
The only thing missing from your videos is time complexity and space complexity of your code. It's very difficult for me to find time complexity of recursive solutions.
Yess Sir these are Amazing but we Seriously need graphs
you are a blessing for many people like me. thank you for explaining everything in such a smooth way.
I like your style of asking people to stop and think in vital positions, helping them to think more deeply and not just mug learn something. Thank you for the efforts!
I wonder how did you study these topics so nicely ?
Thanks aditya for providing us such a great content on Recursion
Great stuff! I'm following this series daily...Please try to upload GRAPHS next..there isn't much good content on Graphs on the internet and your videos would surely help us!
please make graphs simple for us. i know you can do that
Follow striver's graph series, it is brilliant.
Le Striver: Let me introduce myself
In base condition, we can have if(N == 1 || K == 1) since, K == 1 for any N, ans will be 0 only so it might save a few function calls also in this case.
Great!
Or we can just ignore this K == 1 condition and just say if (N == 1) return 0;
bro! it's simple and to the point explaination, first because of length i was going to leave, but the line you mentioned " Your observation is tested" ignited me to continue!..
At 8th minute mark, I paused the video took me 30 minutes to code up a solution involving only recursion and a couple of if statements in Python. The previous videos build up this confidence in me to solve it before watching the video itself. Now I am gonna watch the video and see your approach as well!!
Did you code in paper or ide?
@@thinkingmad1685 paper for logic building and then write the code in vscode
@@Liftsandeats can you share your soultion if it is different than aditya's?
thanks internet for making us meet with aditya's content where we watch for out betterment and thanks us also....recursion and dp god he is for sure
I solved this solution on my own and i was so happy .It happened all because of your teaching .Thanks bhaiya Hats off.
This is by far the best explanation I found for this problem. Thanks.
East or west Aditya boss is the best!!
❤️✌️
if(n==0 || n==1)
return 0;
int mid = pow(2,n-1)/2;
if(k
very good ..
Other way also mentioned below ...apart of recursion ...
if (N == 1) return 0;
if (K
baapre kitna jyada easy bana diya question ko , hats off to you sir
Great Stuff !! Thank you !! People here is the alternative python solution, this relies on the if k is even then we will compliment the output other wise we continue, every time we reduce the value of k by half depending on if k is even or odd. Once again thank you for the great content !!
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
output = self.sub_kthgrammar(n, k)
if output:
return 1
return 0
def sub_kthgrammar(self, n:int, k: int):
if n == 1 and k == 1:
return 0
if k%2 == 0:
# if k is even
return not self.sub_kthgrammar(n-1, k/2)
else:
# if k is not even
return self.sub_kthgrammar(n-1, (k+1)/2)
Or we can just typecast the return value with int()...
Here's my code with little bit of change....
////
def kthGrammar(self, n: int, k: int) -> int:
if(n==1 and k==1):
return int(0)
mid = (2**(n-1))//2
if(k
Thanks for the playlist sir.....your channel is extremely helpful for the placement preparation
When you said this question is only to test our observation skills, i gave this one more try and was able to solve on my own. Thanks
What an interesting problem. All about observation as you said! You explained the problem so well and also the observations, that the solution became so damn simple! When you explained the problem statement, i did notice that first half of next row was same as previous but didn't notice that second half is just complement of previous row.
RECURSION IS LIKE MAGIC INDEED!!
const kthGrammar = function(n, k) {
//Base Condition
if(n == 1 && k == 1){
return 0;
}
//Find the mid of length of the nth row
let mid = Math.pow(2, n - 2);
if(k
It will be better if you mention the time complexity of every problem along with the solution. Thanks!!
o(n) complexity for Time & space
honestly sir you're a great teacher and your explanations are wow..never stop uploading these videos..they are very helpful..
Great thanks from the core of my heart ❤️
today i got the real essence of recursion. ...thanks bhai a lot!!!!!!!
faster than 100% submissions...aditya verma i loved your series
int kthGrammar(int n, int k) {
if(n==1||k==1)
return 0;
else{
int a=kthGrammar(n-1,(k+1)/2);
if((k+1)%2==0)
return a;
else
return 1-a;
}
}
can you please explain this solution.
@@sohamnandi7526 The given code implements a recursive function called `kthGrammar` that returns the value at position `k` in the `n`th row of a grammar sequence. The grammar sequence is defined as follows:
- The first row is always "0".
- For each subsequent row, each element is created by taking the element at the corresponding position in the previous row and replacing it with two elements based on the following rules:
- "0" is replaced by "01".
- "1" is replaced by "10".
The function uses recursion to calculate the value at position `k` in the `n`th row by dividing the problem into smaller subproblems. Here's a breakdown of how the function works:
1. Base Case: If `n` is 1 or `k` is 1, it means we are at the first row or the first position in any row, so the value is always 0. Hence, the function returns 0.
2. Recursive Case:
a. The function recursively calls itself with `n-1` (moving to the previous row) and `(k+1)/2` (finding the corresponding position in the previous row).
b. The result of the recursive call is stored in variable `a`.
c. If `(k+1)%2` is 0, it means `k` is even. In this case, the function returns the value of `a` as it is.
d. If `(k+1)%2` is 1, it means `k` is odd. In this case, the function returns the negation of `a` (1-a).
By using recursion and dividing the problem into smaller subproblems, the function effectively calculates the value at position `k` in the `n`th row of the grammar sequence.
Please note that the code assumes `n` and `k` are positive integers.
Hey @Aditya Verma, thanks a lot for this awesome collections of yours. Your every video is not just a video of any problem, it teaches us so many concepts in many ways that help us later when we revisit such topics again. You are a true gem.
Bhai Graphs par bhi bano do ek playlist , bohot help hoga !! 🙏🙏
God bless you brother. You are a pure soul.
I have no words for your explanation.
Bass itna kahunga ... Aap ho to DSA me aag laga denge bhaiya❤️🥺
Bhai dil se bhot bhot dhanyavaad kya explanation thi bro.
int kthGrammar(int n, int k) {
if(n==1 and k==1) return 0; //this is given in question
int mid=pow(2,n-1)/2; //pow(2,n-1) gives length and '/2' helps to find mid
if(k
Great content, A playlist on GRAPHS please
So wonderful explanation!!! Thank You so much for this Bhaiya!!!
Time complexity: O(n) right?
my approach
def kthGrammar(self, n: int, k: int) -> int:
def rajeev(n,k):
if n==1:
return 0^((k+1)%2)
return ((k+1)%2)^rajeev(n-1,(k+1)//2)
return rajeev(n,k)
Amazing 😍thank you so much for providing great content free of cost
I did this question around 15 days before watching your video but wasn't clear about the basics.. Now it seems i can do this question anytime as you have cleared the basic concept. Thanks bro!. You are awesum as always.. :D
Thank you for such a clear and simple solution
Nice and crisp explanation
** Thank you , Observation is quite important to solve this question
int kthSymbol(int n, int k) {
if (n == 0 || k == 0) {
return 0;
}
int symbol = kthSymbol(n - 1, k / 2);
return ((k / 2) * 2 == k) ? symbol : !symbol;
}
call => kSymbol(n-1, k-1)
works for larger inputs.
final return statement can be changed to
return (k&1) ? !symbol : symbol;
best explanation
Python Solution:
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
if k==1 and n==1:
return 0
mid = 2**(n-1)/2
if kmid:
return (self.kthGrammar(n-1,k-mid)^1)
thnks ..... i got little confused on complement part !!!
Thanks for such a great explanation.
Kya sikha rahe ho bhai, thank you so much.
explicit explanation .. Thankyou sir!
What's the induction condition in this question?
def kthGrammar(n: int, k: int) -> int:
if n == 1 and k == 1:
return 0
mid = (2 ** (n-1)) // 2
if k
Sir how to compliment the function in solve(n-1, k-mid) as m not able to do so. Basically asking how to NOT the 2nd half compared to the n-1 1st half.
Simply use this:
if(kthGrammar(N-1,K-mid)==0)
return 1;
else
return 0;
Take the xor of the return value with 1
@@ujjwal824 thanx bro..
Aditya sir your are legends ❤️
Please upload video on graph 💓💓
please end me time complexity bhi btaya kro, recursive functions me dikkt hoti hai
congratz sir for 2 lakh subscriber
I wonder how did you study these things so well on your own because during your Btech youtube barely had any resources.
We can also done this using XOR of string and add to the end
And after building find k element simple
Time complexity would be O(max(N, K))
Space complexity would be O(N)
And the second method is what you told here I guess
Best playlist for recursion👍
Awesome sir, best playlist for recursion on TH-cam,,plz plz , make playlists on trees
The java bitwise not operator (~) might fuck up your code logic, as it also changes the most significant bit which denotes the sign of the number
Use ternary operator instead
Return (solve (n-1,k-mid)) == 0 ? 1: 0:
def solve(n,k):
if n==1 and k==1:
return 0
else:
if k%2==0:
return 1-(solve(n-1,k//2))
else:
return solve(n-1,(k+1)//2)
print(solve(4,8))
this is a different approach.
we can also find mid by :-> mid = pow(2,N-2); , jst simple maths
you made it very easy! Thankyou! great work!
best explanation ever.
NICE SUPER EXCELLENT MOTIVATED
sahi ho bhai tum, naam suna tha , dekha to acha laga
Can't we use DP in this problem?
Bro I could solve this before watching the video by following your series,
Not only u solve these problems but teach us HOW TO THINK
U r god !!!!
pen coloring (red, blue, black)
if I got a penny every time Aditya said the word 'cool', I would have been a billionaire by now. hehe
jokes aside - you are a bomb teacher!
man this is so cool, the moment you asked me to pause and asked us to observe. I got a different answer.
int kthGrammar(int n, int k) {
if(n==1)
return 0;
int k_ = ceil(k/2.0); // its the previous index of current k, when n-1
int prev = kthGrammar(n-1, k_);
if(k_ == k/2) return !prev;
return prev;
}
Bro same here
But I just complicated it a bit intially
Induction step:-
Val=find(n-1,ceil(k/2))
If ((Val+k)%2==0){return 1}
Else{return 0}
Can u elaborate what you did
Why can’t we do N-1,k//2??
By focusing on the Observation Skills (as per told by you), I just found another way, in which we can reduce the value of K, and that is, by checking the place of K, if it is even we can simply divide it by 2 else we can simply do k/2+1.
int solve(int N,int K)
{
if(N==1 && K==1)
{
return 0;
}
int mid=pow(2,N-1)/2;
if(K
..
.
The solution looks cool!! but some conditions we can eliminate. Here is the code:
false->0 and true->1
-----------------------------------------------------------------
boolean solve(int n,int k){
if(k==1)return false;
boolean e = solve(n-1,(k-1)/2+1);
return k%2==0?!e:e;
}
-------------------------------------------------------------------
recursion is magic.
bhaishab magic tha ye to bilkul magic
Sir please upload videos on graph
The time and space both would be O(N) for this. Right?
bhai bhot acha smjaya, ab smj ari h recursion ko 'leap of faith ' kyu bolte h...thanxx.....
me:yar agey ka smj ni ara kaese kru question
recursion: ruk bhai m krke ata hu sara kam tera,mujper vishvwas rakh
Thanks for watching :D
waah yr ..maja agya aditya bhaiya
Can you prove by induction that the relationship you found actually holds between next rows?
btw what was the induction step in this code?
Very simple recursive solution :-
int kthGrammar(int n, int k) {
if(n==1 && k==1){
return 0;
}
int prev=kthGrammar(n-1,(k+1)/2);
if(k%2){
return prev;
}else{
return !prev;
}
return -1;
}
Bro why you do (k+1)/2 ?
how to find the method for a problem that uses IBH method or ip-op method .
perfectly explained i love it
Amazing explanation 💕🙏
What change should be done in the code to print this grammar instead of getting a single bit ?
Nice solution and very well explained. What is the time and space complexity of this approach?
I tried in a different way.
def kthGrammar(self, n: int, k: int) -> int:
def recursion(n, k):
if n == 1 or k == 0:
return 0
val = recursion(n-1, k//2)
return val if k % 2 == 0 else (val+1)%2
return recursion(n, k-1)
very beautifully explained!!
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
# base case
if n==1 and k ==1 :
return 0
length = 2 ** (n-1)
mid = length / 2
if k mid:
return 0 if (self.kthGrammar(n-1,k-mid)) else 1
Time Complexity?
what will be the time complexity of this code?
Excellent explanation.
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
if n == 1 and k == 1:
return 0
bit_size = 2**(n-1)
print(bit_size)
mid = bit_size//2
if(k
Thank you sir !
This question was great!
k/2 bhi use kar sakte hai na 🤔🤔
I understood how it is working but I am not getting why it is working? If I take an example say(3,3) and back trace it from the base condition to first function call. It is giving me right ans bhut why it is giving correct ans? That i am not getting. Plz can someone explain.
Why solving this using queue data structure, I'm getting TLE ?
how can u compliment by just putting a ! sign in code plz can u explain it or share a link that will help me
can anyone please suggest good resources to learn 2 pointers?
Thank u so much...u are awesome!!!