Find Kth Bit in Nth Binary String - Leetcode 1545 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem find Ki bit in nth binary string so pretty challenging problem today I'm going to be going over two solutions I mean I will conceptually explain like The Brute Force solution but I will not be coding that one up I'll then be going over a recursive solution for this problem and then we optimize the space of that solution with an iterative one I'm not able to spell today so I give up the idea is that we're given a binary string that looks like this so it's it's just zero right now and for the record it is a string it's not a number so this is Nal 1 and then we can form the next uh strings like this by taking this itself so that's over here and then put a one in the middle and then take this string and it involves a two-step process first we invert the string so every zero will turn into a one and every one will turn into a zero this string is pretty simple we just turn it into a one and then we take that itself that new string that we formed and then concatenate it over here so this is the middle value this is the left portion the left portion comes from the previous string the right portion in a sense also comes from the previous string or it also comes from like the left side of this which these are equivalent and that's going to be a very important observation when we solve this problem but of course like there is that two-step process and that's kind of where the difficulty in this problem comes from the inversion and the reversal let's continue for a second so now if we wanted to form the next string the one at level Nal 3 this was at Nal 2 we would just take everything here move it over there so nothing new here you might be noticing the pattern where like the first half of each of these strings is always going to come from the previous one then the middle value the middle value is always going to be a one and then the right portion of the string how do we build it take this invert it you'll get something that looks like this 1 0 0 then take this and reverse it you'll get something that looks like 0 01 and then take that and then place it over here and I could keep going but I think you probably get the idea so down here the middle value is right over here this is identical to the stuff over here okay now that we kind of understand the setup of these strings what exactly do we want to do well for the Ki string we're given a variable a parameter K in this example let's say k is equal to 1 and we're also given a parameter n = 3 that means we want to know what's the Ki bit in the nth string so that means in this string what's the first bit and so I guess this is indexed by one like the string itself so this would be position one and this would be position 7 so we want to know what bit is set here now the obvious approach would be the Brute Force solution take the initial string build the next string build the next string keep building strings until you get like the nth string once you get the nth string if you have it in memory you can just just look at the K position I guess since K is equal to 1 we would probably look at index K minus one that would give us this position but anyways very reasonable solution and at first you might think it looks like a linear time solution because it's just like a one step until we get to the nth string and then we just index that position but technically since the length of the string is doubling every single time we start with a string of length one if we're at some arbitrary string the size of that string is going to be proportional to 2 to the power of n because we're doubling the length of the string every time to build this string we have to you know do the two to the power of n and the space complexity is also going to be proportional to 2 to the^ of n the constraints of this problem actually allow us to solve this problem in a Brute Force way I think n is going to be up to 20 so relatively small but I want to show you a better solution so before I even get into the solution I'm just going to make a bunch of observations about this problem because those are very important most people can't just jump straight to the solution unless they make these or they kind of have the intuition Behind These so first let's recognize that if we were ever going to ask like what's the first bit well then we're always going to return zero because it never changes look this position it never changes in fact none of the positions ever change this position never changes this position never changes neither does this one neither does this one neither does this one or this one I mean technically you could say that sometimes like that bit isn't set yet so like here it wasn't zero or one but once a bit is set it never changes if you don't make that observation you really don't have a chance of solving this problem more efficiently and it's not like it's a difficult observation to make if you're actually trying to make observations if you're just trying to figure out what the solution is without making any observations then yeah you might miss it you might not notice it you might gloss over this fact but now that we know this how can we use that to our advantage well suppose I changed this problem a little bit suppose I'm looking for the seventh bit in the fourth string so that would be this bit over here this is the the seventh one in the fourth string now how do I figure out what that is well I have no idea what that is but I do know this well I guess I don't know this yet but if I knew what the length of this string was and by the way in this case it's 15 if I knew that then I could ask this very simple question what's the Midway point of this string obviously that's here is this bit on the left of the Midway point or is it on the right of the Midway point because it's if it's on the left then I can just change this sub problem and say well I'm not really looking for the seventh bit in the fourth string I'm actually looking for the seventh bit in the third string so now I'm over here I'm no longer looking at this problem I'm looking here so let's ignore this now and try to solve this sub problem over here what's the seventh bit in the third string well once again I'm going to ask myself what's the length of this let's assume we already knew it the Midway point is at position four I'm looking for the seventh bit clearly I'm on the right side and by the way before I get into what we're going to do when we're on the right side notice that there are three cases either we're on the left side in which case we can just you know go to the smaller string in the same exact position or we're on the right side and I'm going to tell you how we're going to handle that case but the third case is when we're in the middle when we're exactly in the middle middle of the string remember how these strings are being built in the first place we can build this string by taking the previous and then putting a one in the middle and then you know inverting it and reversing the left side to put it over here so in other words the middle of every single string is always going to be one so if we were ever looking for the kith position and that happened to be in the middle of a string we would immediately return one in a sense that's kind of a base case like that's the easy case so now that we are on the right side what should we do because this is the difficult part this is probably the reason you're watching the video well remember how this string is being built in the first place we start with this over here which is 0 1 1 we invert it which is going to get us to be 1 0 0 then we reverse it which is going to be 0 0 1 in other words if this string is position 1 2 and 3 this bit is actually going to come from this bit this bit is going to come from that one and this bit is going to come from that one specifically this is going to be the inversion of this bit this is going to be the inversion of that bit and this is going to be the inversion of that bit so like if we're looking for this bit over here if we can figure out what bit is over here then we can just take the inversion of that bit and say okay that's the bit that's set over here so if we figure out that the bit here is a zero we'll say okay then that must mean the bit over here is a one so how do we do that in terms of like the sub problem though cuz it's good that we're looking at the first half of the bits because that will allow us to now go back here because rather than asking well what's the first bit in the third string we can ask what's the first bit in the second string because we know for sure that everything over here is exact the same as everything over here but how do we calculate the position right now we were at k equal 7 how do we get this position here and this is another tricky part it's not like insanely difficult but I can see how somebody would get stuck here let's just take a look at that string itself it looks something like this where this is the Midway point and I'll put the positions of each of these like this imagine we were here we know that this is going to correspond to that like let me just kind of draw these out so this corresponds to that this corresponds to that and this corresponds to that and the middle is by itself how do we map 7 to 1 how do we map 6 to 2 how do we map 5 to 3 at first it seems kind of difficult but it's not as difficult as it seems what we can say is if we're at this position calculate the distance from here until the end of the string that distance is zero we can take that distance and add it to the first position which is one so basically seven maps to one we can do the same thing here what's the distance from here until the end of the string that's 7 - 6 that gives us a distance of 1 so now from the starting we want to do a distance of one so 1+ one will land us on two same thing over here the distance from 5 to 7 is 2 and the distance from 1 to 3 is also two so five maps to three basically what I'm saying is if we are on the right side of the string we can go to a sub problem we can decrement our n but we also have to update our K our K can be updated like this K is going to be one starting from the beginning of the string plus the distance from uh the length the end of the string to a k so length minus K that's that distance and we add that to one so now the sub problem becomes this I'm going to draw it down here first the sub problem became n = 3 K = 7 and now the sub problem is going to be n = 2 K is equal to 1 now but don't forget to invert the result of that so what I'm going to do is just keep track of a Boolean and I'm going to call it invert initially it's false but now that we were on the right side we want to know what bit is set here like what is this bit it's zero if we were to determine that we could invert that and then we'd know the result is one so now I'm going to set my invert variable to true so whenever we figure out the result just invert it and that will give us the final result this is a minor detail that we can focus on in the code so don't pay too much attention to this just yet but now we're over here we're going to do the exact same thing figure out the Midway point right now our K is equal to one so we're actually on the left side of the Midway point so now we will say that this bit is going to be the exact same as the bit in the smaller string at n equals 1 so now we are at nals 1 and that's a base case as soon as n equals 1 we don't have to go any further because we're going to assume that the K is valid it must be it's not like we're ever going to get here and say well what's k equals 2 that wouldn't happen because if it did we would have just returned the middle value from here anyway or we would have been in the right side in which case we would have mapped over here so from here we're going to return zero back here and from here we're going to return zero back here and from here we're going to say okay well whatever that result was I wanted to invert it so now I want to return one back because this zero tells us that there's a one over here and that tells us finally that the K bit in this string was a one so this is kind of the intuition and sort of a dry run of the solution this might be enough for you to figure out what the code is by yourself if not I'll go ahead and show you what the code is and you can kind of tell that this is going to be a linear time solution because we're starting here and we're going to keep going in the worst case until we reach here or maybe we can stop early if we reach like the halfway point of a string if K happens to be the halfway point of a string string space complexity though because of the recursion I'm going to solve this recursively first and then iteratively after that the recursion is going to be n space actually uh one last thing I forgot to mention was how do we do like the lengths of these strings because since we are starting at Nal 4 like we're starting here and then working our way backwards what's the length of that string going to be well you could compute it with a loop you could compute that in O of n time you could start with one multiply that by 2 plus 1 that's going to give us three multiply that by 2 + 1 that's going to give us 7 etc etc you could do that but if you notice these values actually are just 2 to the power of the level minus 1 this is 2 power of 2 - 1 etc etc and that's kind of reminiscent if you know like the size of a binary tree if you have a full tree with just one level that would look like this if you had a full tree with two levels that would look like this if you had a full tree with three levels it would look like this and that would have seven nodes so that's just like a little bit of the intuition but anyways let's now get into the code I want to have a helper function and I want to solve the original problem given the length instead of just keeping track of the level because if we do that then inside of here we're going to have to recompute the length every single time like if I did this instead if I had n and K and then in here I said well my length now is going to be 2 to the power of nus1 like I could solve it this way and then from here I could return helper of N and K this is very nice because then we actually don't even need an inner function we could just do it all out here but rather than Computing the length every single time I'm just going to pass in the length itself rather than n and then we can move this out here and then we can pass in the length here and then we don't have to keep recomputing the length and the base case is going to be the same anyway like if n equals 1 we know for sure that the length also equals one so we can do this and then in the base case we can just return zero don't return the integer zero make sure you do the string okay now that we have kind of the setup let's actually implement the function let's calculate the halfway point so we can do that like this length ided two and then there are three cases either we're in the left side um just to do the math real quick if we had 15 and we integer divide that by two we're going to end up getting seven because it's going to be 7.5 and we're going to round down so the Midway point is actually going to be half + 1 so we know we're in the left side of the string if K is less than or equal to half we're in the right side of the string if K is greater than half + 1 because half + 1 is the Midway Point uh the last case else is if we were actually in the Midway Point notice that the lengths are always going to be odd because the length of a level is computed by 2 * the previous level plus 1 this is always going to be an even number if we add one to it then that's going to make this thing odd so now the else case remember is very simple we're in the middle of the string so we can always return one in that case if we're in the left side then it's going to be the recursive case it's going to be pretty simple we just take the length and get the half of that length we already computed that and then pass in K cuz the position is not going to be different in this string versus half of that string so this can be returned now this part is going to be a little bit more tricky we still want to go to the smaller string which is of half the length so we can call helper of half but what position are we looking for now remember we're looking for a position on the left side of the string now our K happens to be on the right side so we have to make it valid and we have to make it correct we can do that like this one starting from the beginning of the string and then calculate the distance from K to the end of the current string which is length minus K and then take all this and add it to one so this works out but here we're not going to return that because we have to invert the result of that so I'm going to set this to a variable result and I'm going to return Z if result is equal to 1 so whatever the result is return the opposite now if the result is not equal to one that must mean it's equal to zero in that case I want to return one instead either way I'm returning the inversion this is pretty much the entire code I believe it's correct let's run it and yes it is and it's pretty efficient though we actually can improve the memory you can see from this recursion the call stack is going to be of size o of n it's not too difficult once you come up with a recursive solution to optimize it into a bottomup solution the code is going to be very similar I'm going to have my length here I'm going to say while we haven't reached the base case while the length is greater then one I'm going to compute the half so pretty much taking from the code below I'm going to do this and then I'm going to set up my conditions the exact same way I'm going to copy all of these and then put them here the only thing is we're not going to be calling any helpers so let me clean all of this up now if we're in the left side of the string what do we want to do K should stay the same in that case just like the recursive solution but the length should be updated to be half the length now so length should be set to half that's pretty much it that's all we really did in the recursive case as well if we're on the right side of the string what do we do well in that case k has to be updated K has to be updated to 1 plus the length minus K we also are going to update the length as well make sure you put this line after the line above cuz you want to use the original length not half the length when you're Computing this there's one other thing how do we handle this part the fact that the result should be inverted well the easiest way is to just have a variable in my opinion I'm going to call it invert I'm going to initially set it to false if we really wanted to we could have actually used this also in the recursive solution and I actually might as well show you how we're going to do that in the recursive solution we could have had a variable invert and then we could have passed a variable in for the recursive function here for invert we'll pass in false initially and then for this we'll just pass in the variable itself and then here we can get rid of the Turner operator we can turn this into a regular return statement and we can also pass in the variable invert here but every time we execute this case we're going to swap this we're going to negate it so if it was false we'll set it to true if it's true we'll set it to false because if we're going to invert two times we're going to end up back at the result remember if you take zero and you invert it you get one if you invert one you get zero so if we invert twice this should be back to false okay now the only thing is to change like these two base cases we'll return one here if not invert otherwise if invert is true we'll return zero because that's the inversion of this value we're going to do the same thing up above here so if not invert do this otherwise return one instead said so I'm going to quickly run this to show you that it works let me just comment out uh this part and looking at the left side you can see that that works as well so that's the idea I'm going to use in the iterative solution because we can't really just do it the original way that we did so here I'm going to change this and now in this case the other case here where we do want to invert we're just going to set the invert variable to be the negation of what it was uh before so like that how should we handle this base case should we always return one if we're in the middle of a string not necessarily we now have to check the value of invert just like we did in the recursive solution so return one if not invert else return zero we're almost done now what would happen if we reached the base case where the length of the string is equal to one well we know that the bit in that string is always going to be zero so what should we do should we always just return zero here not necessarily we have to check the value of invert if not invert then we return zero otherwise we would return one just like we kind of did in the recursive Solution that's pretty much all for the iterative solution you can see that it is very very similar to the recursive solution so I'll go ahead and run this as well and you can see that this works and the big o space complexity is more efficient leak code doesn't always indicate that but if you found this helpful check out n cod. for a lot more thanks for watching and I'll see you soon