K-th Symbol in Grammar - Leetcode 779 - Python
Vložit
- čas přidán 9. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑💼 LinkedIn: / navdeep-singh-3aaa14161
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/k-th-sy...
0:00 - Read the problem
0:30 - Drawing Explanation
6:54 - Coding Explanation
leetcode 779
#neetcode #leetcode #python
This was difficult man. I was trying to solve it brutely by forming vectors of every level. It gave me memory limit.
I tried the same thing , came here for the solution
same..approach..but memory limit exceeded error.. actually it's because of n..it's so huge.. that k also getting larger. dunno 'long' type can handle or not instead of 'int'.
@@starkendeavours7072 No, actually the memory limit hit because of the size of vector, not the data type of the vector.
Took me 3 hours to write my 4 line of code with TC-O(logN) and SC-O(1)
Just count the number of 1s in the binary representation of k - 1. If that number is odd, then return 1, otherwise 0.
Explain: First, we observe that the first half of the n-th sequence is exactly the (n - 1)-th sequence, and the second half is obtained by flipping every bit in the first half (proof by induction). So, we don't need n here, we have an infinite sequence whose the 2^(n-1) first elements is the n-th sequence. Let's reindex this infinite sequence from 0 instead of 1. By the proposition mentioned above, we have the k-th value of this infinite sequence is just the opposite of the (k - 2^i)-th value where 2^i 0:
result ^= k % 2
k //= 2
return result
My my! Using math, then recursion and then this binary search. This problem has a lot of punch.
Same solution but recursively
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
if n == 1 and k == 1: return 0
mid = (2 ** (n-1))//2
return int(self.kthGrammar(n-1, k)) if k
inside else condition we can just do cur ^= 1 (xor with 1) the no. will flip by itself... btw amazing solution.
Thank you for the great explanation.
Similar to yours but without using n. We start at kth_bit=0 and for odd k, we do k+1 and for even k, we do k/2. The bit at new k gets flipped.
Solution:
kth_bit = 0
while k > 1:
k = k + 1 if k & 1 else k >> 1
kth_bit ^= 1
return kth_bit
Not easy for sure. Love the way you explain.
Thanks For Uploading everyday it helps alot
These are the type of problems (which have 3+ solutions) expected in interviews.
res,root = 0,0 # Lets presume that the kth indexed symbol is 0
for i in range(level-1,0,-1):
# if position is even, then its parent must be opposite
if pos%2 == 0: root = 1 - root #toggle the parent
pos = (pos+1)//2
return root if root == 0 else 1 # If our assumption is correct, then 0 else 1
Thanks for explaining your solution!
This question was really good , I had to see the solution to solve this one. Especially the solution where you have to count no of set bits in k-1 and return 1 if its odd otherwise return 0 . This solution blew my mind . I was like how do people think about these solutions. Loved your video by the way
Genius!
I solved it Using recursion but your solution is really easy and nice
You are amazing
You can actually just see the branches to take from the bits of (k - 1). For example, when it's 0 (all zero bit), you always go left, when it's 2^n-1 (i.e. n ones), it's always right. If it's 1, that's a bunch of 0 bits and a final one, i.e. always take the left branch until the last level. And you can then even compute the new digit on the current branch with "previous_digit xor bit_in_k_minus_1_at_curr_level" (conceptually, flip the number if we're at a 1-bit i.e. going right, otherwise keep it the same). In general, also neat to know that you can flip between 0 and 1 with "prev xor 1" or "1 - prev".
could you give the code for this plss
@@NishanPnab
k -= 1
curr = 0
for i in range(n - 2, -1, -1):
curr = curr ^ ((k >> i) & 1)
return curr
💥💥
Holy mother teresa!!
Subarrays Distinct Element Sum of Squares II .. do this question please .
Other solution : Reverse engineer using bit masking
Observation => for n = 4
0
0 1
0 1 1 0
0 1 1 0 1 0 0 1
If u see we have pattern repeated with toggled, we can start from k and move back instead in O(logn) time
so ain't we supposed to store these too?...before we move back and find the element ??
Sir one question i have in dynamic programming can u please give answer
Count the number of unique subsequences which have equal number of 1s and 0s in given binary string can u please give solution
How about this ?
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
if n==1 :
return 0
if k%2==0 :
if self.kthGrammar(n-1,k//2)==0 :
return 1
else :
return 0
else :
if self.kthGrammar(n-1,(k+1)//2)==0 :
return 0
else :
return 1
Hi, can you make video how you making your CZcams video
Using recursion
class Solution {
public int kthGrammar(int n, int k) {
return recursion(k-1);
}
private int recursion(int k) {
if(k == 0) return 0;
int p = (int)(Math.log(k) / Math.log(2));
int r = (int)Math.pow(2,p);
int ans = recursion(k - r);
return ans == 0? 1: 0;
}
}
I thought I found an algorithm to find the value for k. Boy was I wrong...
Hello,
during an interview is it useless to solve a problem but with a bad O in time/space ?
I often find a solution for a problem but not with good O
Thank you :)
Hey! From my previous experiences it is definitely not useless. Solving the problem should be the first priority and the interviewer will genuinely value it and they might expect an optimised solution but that is not mandatory in all cases but preferrable.
@@gangstersofsona8486 thank you 🙏
getting memory limit exceed.
A recursive solution
public class kthSymbolGrammar {
public static void main(String[] args) {
int n = 5;
int k = 4;
System.out.println(kThSymbol(n, k));
}
static int kThSymbol(int n, int k) {
if (k == 1 && n == 1) {
return 0;
}
int mid = (int) (Math.pow(2, n - 1) / 2);
if (k
wrongly categorised as "medium"
public int kthGrammar (int n,int k){
if(n==1) return 0;
if(k%2==1)
return kthGrammar(n-1,(k+1)/2)==0?0:1;
return kthGrammar(n-1,k/2)==0?1:0;
bit .
int count =Integer.bitCount(k-1);
return count%2==0?0:1;