Binary Prefix Divisible By 5 - Leetcode 1018 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem binary prefix divisible by five. It feels a little bit awkward uh making another elite code video after that last video I just made. Uh but anyways, let's get into it. So this is a pretty uh interesting problem, I guess, for an easy one at least. So we're given a binary array, meaning it's only going to contain zeros and ones. And basically they tell us that every I mean they don't use the word prefix. I guess they don't use it anywhere in the description, but they use it in the title. So title is kind of more descriptive than the problem statement. But basically every one of these prefixes here from the beginning to the end of the array represents a number. It's the binary representation of a number. And they make it pretty easy for us because the order the relative order of these is going to be preserved. So like they use this example and they say the first one is just one. And the reason they say the second one is two because you just take the second like the first two digits and then read them from left to right. The binary representation of two. That's what we have over here. And then lastly this one whether you go left to right or right to left it's the same but we still go left to right. And this is the binary representation of five. So for this we have the uh zero here which of course is going to be zero. And then here we have 0 1 which of course is uh one and then here we have four. So 0 1 1 and then that's going to be four. What we want then of all of these is we want to create an array of the same size as this. And so the first one we just want to know is this divisible by five. So we get that by taking this modding it by five. If we get a zero then it's divisible by five otherwise it's not. Right now this is. So then we can put a true in the first slot here. Second one 5 we're going to get a remainder. So that's false. 4 5 that's also false. So that's why this is the array that we would return for this. Couple parts to this question and really the trickiest part is the fact that the size of this array you have to be careful because the size of the array I think in the worst case could be this. And the key thing to note here is this is bigger than 32 and bigger than 64. So in most languages where you're going to probably use a 32 or 64-bit integer, this is too big for that. Python doesn't have that problem. So, you can kind of just get away with not reading the constraints in Python, but I feel like that's cheating. I'm probably I'll show you the code in Python. It's pretty similar to the code in C++, but I'm going to do the C++ one as well because I want to show you that the naive solution is not really going to work for C++. But the real solution, the better solution isn't much more difficult. So, first I want to show you how you can actually build these integers. It's pretty straightforward. Uh for the first here, we're just going to get a zero. For the next one to build this, we're going to take this zero, shift it to the left, and then we're going to get an empty slot over here. Empty slot is just another word for zero. So to that empty slot, we can take this bit and add it there. If it's a zero, nothing's going to happen. If it's a one, we're going to get that. So you can see it does look pretty correct. So same thing, if we want to build the next one, we take this entire thing and shift it to the left. You get zero, one, empty slot. Then you take this, you add it there, you get a one, and then you get what you want. Okay? So, building these isn't super hard. And then taking them, modding them by five also isn't super hard. But watch what's going to happen here. What if I had this big string of ones? And so, I don't even know what number this is anymore. Let's say I have a really big string of ones. Let's just say there's 10 of them for now. There's 10 one digits. I mean, the way I'm going to code this up, this would never happen, but I'm just trying to show you this. Like, this would never be more than like 32. And it would probably be much less than 32, actually. But, uh, so let's say we have these. And then let's say we have three more slots here. So, let's say that this here is any number except five because five can be represented with this right here. 1 0 1 is five. So there's two cases. This is kind of the thought process you have to go through here. There's two cases. Either what we have is divisible by five or it's not divisible by five. So if it is divisible by five, that's the easy case here because what's going to happen when you take a number like this one and you mod it by five, you're going to get zero. So my claim to you is when you take this number let's just call it cur whatever the current number is and then you mod it by five and let's say you get zero. My claim is we can safely replace the entire number the entire current number we can replace it with zero because it is divisible by five. And I'll show you why that's not going to negatively impact the next number that we end up looking at. And the answer is pretty simple because we take the current number. It's all we know is it's divisible by five. We don't know what the rest of these digits are. We don't really care. We don't care what number this ends up forming. It's divisible by five. Okay. And we know that when we look at the next number, all we're going to do is take cur and then shift it to the left by one. And then we're going to add whatever the digit that we look at, let's call that n. So why is it that if we ended up reassigning this to zero rather than the actual number that it actually was, why isn't that going to neg negatively impact anything? Because shifting a number to the left is equivalent to multiplying it by two. Cuz that's just like the definition of binary. Everything in the onees place goes to the two's place. Everything in the two's place goes to the four's place. Everything doubles. So if you take a number that was already divisible by five, then you double it. It's still divisible by five. If you double it again, it's still divisible by five. So, it doesn't matter that we got rid of it, that we we reset it down to zero. It doesn't matter. That was a good thing for us to do because now we don't have to take up too many bits. We're not going to get that overflow issue. So, that was the good thing about that. And then since we're not looking at those anymore, now we can actually focus on the relevant digits, the new digits. So, there's that case. Now, there's the other case. What if this was not divisible by five? Well, whatever it happens to be, it could either be less than five. So maybe it's something like this. It's four. Well, then it's going to stay the exact same. So taking cur modding it by five, it's going to leave it at what cur was if this is less than five. Now, it's true that we would end up getting rid of everything over here. But that's okay because none of those digits are even relevant anymore in terms of determining if this guy is divisible by five. So that's why uh this is good. Reassigning this after modding it by five is good cuz we're getting rid of the unnecessary digits that wouldn't even contribute in the first place. Now the other case is what if this number is not divisible by five but it's bigger than five. Well that would be something like this. I think that's a seven. So in this case we're kind of doing the same thing that we did where we chopped off all these digits but in this case we're not really fully chopping off the digit but we're saying that okay this is seven. uh after taking seven modding it by five we get two. So we're saying that we can take this and we can reset it down to two. And the reason that's fine is because when we take this two now and we shift it to the left, it's going to become a four. So if I just do the math for you, which is we had seven, what we would have originally done is we would have shifted that to the left and it would have turned into a four. And then if you take that and you mod it by five, you would get four, right? You'd still eliminate the two fives. Now, I didn't do that. I took seven, I modded it by five. Then I got a two left over. And now I'm going to shift that to the left. So now it's going to become a four. You mod that by five, it's still a four. So the math works out in every one of these cases. And I if you thought that this was kind of overexlaining why this works, I would partially agree with you because the main intuition, the main intuition of why all this stuff works is the fact that we're taking this number, we're shifting it to the left, which is effectively doubling it. And doubling a number is not going to cause any problems. It's not going to make anything inconsistent when we're modding that number by any number. Whether it was five or whether this was a prime number, it wouldn't matter because by definition, if n is divisible by five, then 2 * n is also going to be divisible by five. If it was not divisible by 5, then by definition, 2 * n is also not going to be divisible by five. And also that the the number the modding is going to be consistent. The result is always going to be consistent. But anyways, this explanation got a little bit messy. So if you still don't understand it, I think you will once I get into the code. So, let's go ahead and do that. But, does anybody have any questions? Huh? There's nothing wrong with having questions. Okay, that's not what I was trying to say. I just think that people are doing themselves a disservice if they don't at least try to answer their own questions because I think a lot of the time people are smart enough to do so. They just don't believe that they can. It's all I was trying to say. Okay. So, I'm going to go ahead and create my result array. I'm going to keep track of my current number zero, which is initially going to be zero. I'm going to go through every number in my list of nums and I'm going to take the current number and I'm firstly I'm going to shift it to the left initially when this was zero. It's not going to do anything. So that's fine. Then to that I'm going to add the current number and whether it's zero or one. I'm going to assign that back to cur. I'm not going to do the modding. I'm not going to update cur with the mod. I'm I'm going to use the mod with the result. So before I append to the result, I'm going to say is cur divisible by five. If that's zero, then this is obviously going to evaluate to true. If it's not, it's going to be false. And then here I can return the result. And this works in Python because integers are arbitrarily large. They are we're not going to have to worry about any overflow. And so on the left here, you can see that it works. It's pretty efficient. But there is a bug with this. And the bug doesn't really show until you use a different language. So this is pretty much the same code in a C++. I'm taking the number, shifting it to the left, adding n, and then I'm taking the boolean, and then appending that to the result. And if I try to run this, we're going to get an error. And notice the example right here. Notice this example right there. How many integers do we have here? Well, if you're too lazy to count, um, I just do like a quick controll. So, I'm going to control F for the comma. So, you can see the first one is the second one on the page. And I'm just going to keep going through this until we get to the last one. And you'll see that this is the 39th. So obviously this is more than 32. I was trying to store it in a 32-bit integer. And that's why we had an issue. It overflowed. So we can take this and mod it by five so that this cur will never be bigger than 32. And in fact, it'll never be I don't think any bigger than like a three or four bit integer. And then we can use that and still mod it by five and see if it was divisible by five. And again, by doing that, we're not messing up the number for future iterations because every time we shift it to the left, it is doubling, which is not going to cause any problems. So now I'm going to just go ahead and take this and run it. You can see here, this one works now, and it is efficient. Okay, but seriously, does anybody does anybody have any questions? because I can think of at least one pretty good question and I didn't cover it in this video. So, you might honestly have had that question, especially if you're somebody who, you know, thinks pretty deeply about things. I talked about how overflowing is going to mess things up. But why is it going to mess things up? What's going to happen if it overflows? Because I mean, let's say we have a 32-bit integer. And let's let's just say let's just use a few ones, right? And let's say these are the most significant bits. So let's say this is the 302 bit, the most significant one. And so when I bit shift that to the left, I'm getting rid of that information. When we mod by five, I said getting rid of that information, that's not a problem. And I kind of explained why. But why is shifting this to the left and getting rid of that an issue? That's not modding it by five. That's not getting rid of a multiple of five from this number. That's getting rid of a power of two, a very significant power of two. So like 2 to the power of 31. And the reason that's a problem is because that number is specifically not a power of five. If it was a power of five, it wouldn't matter. If this problem was prefixes divided by two, that would not be a single problem for us. It wouldn't matter. The fact that it's not is like imagine that shifting it to the left is getting rid of like 17 from the original number. Obviously, that's going to cause issues cuz that's not a multiple of five that we're getting rid of, which just cancels everything out. This is different. That has a remainder of two. That's going to mess things up. So, that's why. Anyways, I think most people probably don't really care at this point, but I find this stuff really interesting. I find it worth thinking about, I think. But anyways, if you found this useful, check out necode.io for a lot more. Thanks for watching.