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'.
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
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
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
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
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
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; } }
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".
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
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.
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
![ILLSLICK - KILLSHOT REMIX [FULL VERSION]](http://i.ytimg.com/vi/RIK8RrqIAzE/mqdefault.jpg)
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.
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
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
Took me 3 hours to write my 4 line of code with TC-O(logN) and SC-O(1)
My my! Using math, then recursion and then this binary search. This problem has a lot of punch.
inside else condition we can just do cur ^= 1 (xor with 1) the no. will flip by itself... btw amazing solution.
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
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
Thanks For Uploading everyday it helps alot
Not easy for sure. Love the way you explain.
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
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
q = [0,1]
gMin, gMax = 1, 2 ** (n - 1)
for _ in range(2, n+1):
half = (gMax - gMin + 1) // 2
leftEnd = gMin + half - 1
rightStart = leftEnd + 1
if gMin
Thank you for the great explanation.
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;
}
}
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
Thanks for explaining your solution!
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 ??
I solved it Using recursion but your solution is really easy and nice
Holy mother teresa!!
Genius!
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 🙏
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
Subarrays Distinct Element Sum of Squares II .. do this question please .
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
💥💥
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
Hi, can you make video how you making your TH-cam video
getting memory limit exceed.
wrongly categorised as "medium"
I thought I found an algorithm to find the value for k. Boy was I wrong...
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;