K-th Symbol in Grammar - Leetcode 779 - Python

[@rushabhlegion2560]

This was difficult man. I was trying to solve it brutely by forming vectors of every level. It gave me memory limit.

[@karthiksuryadevara2546]

I tried the same thing , came here for the solution

[@starkendeavours7072]

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'.

[@rushabhlegion2560]

@@starkendeavours7072 No, actually the memory limit hit because of the size of vector, not the data type of the vector.

[@ngneerin]

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

[@SumitKumar-qg4ps]

Took me 3 hours to write my 4 line of code with TC-O(logN) and SC-O(1)

[@swastikgorai2332]

My my! Using math, then recursion and then this binary search. This problem has a lot of punch.

[@shubhdangwal4190]

inside else condition we can just do cur ^= 1 (xor with 1) the no. will flip by itself... btw amazing solution.

[@StellasAdi18]

Not easy for sure. Love the way you explain.

[@satyamjha68]

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

[@VenomIsLazy]

Thanks For Uploading everyday it helps alot

[@arihantbedagkar7678]

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

[@jonaskhanwald566]

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

[@gregoryrobertson]

Thank you for the great explanation.

[@Cheng-K]

Thanks for explaining your solution!

[@1vader]

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".

[@NishanPnab]

could you give the code for this plss

[@1vader]

@@NishanPnab k -= 1 curr = 0 for i in range(n - 2, -1, -1): curr = curr ^ ((k >> i) & 1) return curr

[@binfos7434]

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

[@abhishek_dagar]

I solved it Using recursion but your solution is really easy and nice

[@PraveenKumarBN]

You are amazing

[@sandeshprabhu2988]

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; } }

[@VidyaBhandary]

Genius!

[@devkumar9889]

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

[@starkendeavours7072]

so ain't we supposed to store these too?...before we move back and find the element ??

[@abhilashpatel6852]

Holy mother teresa!!

[@pritz9]

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

[@maurocarlucci8643]

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 :)

[@gangstersofsona8486]

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.

[@maurocarlucci8643]

@@gangstersofsona8486 thank you 🙏

[@Coldgpu]

💥💥

[@TheBackendDeveloper-b6t]

Subarrays Distinct Element Sum of Squares II .. do this question please .

[@thor1626]

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

[@kanjarlanarasimha2605]

Sir one question i have in dynamic programming can u please give answer

[@kanjarlanarasimha2605]

Count the number of unique subsequences which have equal number of 1s and 0s in given binary string can u please give solution

[@bundiderp5109]

I thought I found an algorithm to find the value for k. Boy was I wrong...

[@SonuRaj-er1hn]

Hi, can you make video how you making your KZbin video

[@ksvijayan06]

getting memory limit exceed.

[@Jargal200]

wrongly categorised as "medium"

[@dayashankarlakhotia4943]

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;