Smallest Integer Divisible by K - Leetcode 1015 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem smallest integer divisible by K. And it's worth mentioning that this problem is basically just a combination of two different problems. And at least the two ones that I can think of is the first one is just yesterday's problem. In case you don't know which one I'm talking about, I'm talking about this one 108. And the other problem, the only reason I probably even remember it is because it is a part of the neat code 150 list. If you go to the math and geometry section, it is this easy problem. And we're going to use the exact same technique we use in this problem to solve today's problem as well. So with that out of the way, the idea of this problem is that we are given a positive integer k and the constraint on that parameter is going to be 10 ^ of 5. And what we want to do is find the smallest positive integer n. well rather the length of it. And we want n to be divisible by k and n can only be made up of one digits. So in increasing order the numbers that satisfy that last condition are going to be just one then two ones then three ones and then you keep going. And keep in mind this is not binary. This is still base 10. When I see ones and zeros, I get kind of confused and I start thinking in terms of binary. So don't do that. This is still base 10. And conceptually like the brute force would be pretty easy, right? What we would do is we would just try this one. Is this one divisible by K? If it's not, you just keep going. You just keep trying. But there's a few problems with that approach. And the first one is that actually it's possible that there's no such n where the number is going to be divisible by k. There's no number with all ones that's going to be divisible by k. And I can think of at least one such example off the top of my head because every single one of these is always going to be an odd number because the last place is always going to be a one. So when you know that, you realize that not a single even number will ever be able to divide these because an even number like we'd have to multiply this by something to equal one of these odd numbers. And that's just not possible because when you know with like an even number, if you take an even number, you add another even number to it, it's still even. You add another even number to it, it's still even. It's always going to be even. It's never going to be odd. So that's like one case if you were wondering when that would ever happen. But there's going to be other cases as well. So we're going to need to know some kind of general way to figure out that the number is not ever going to be divisible by K. When I saw this, I like the first thing I thought of was that problem I just showed you like where you have to do cycle detection with a number. So I was already thinking in terms of that. So, the main reason I guess I was able to figure this out quickly was just because I've I've seen this pattern before. But they mention another thing before we even get to the cycle detection. They mention that n actually might not even fit in a 64-bit integer. So, the first number that we see that satisfies the conditions might have more than 64 bits like in the binary representation of it. So if that's the case, then obviously in trying to build these numbers bigger and bigger, we're going to get the same issue that we talked about yesterday, which is overflow. And the solution to that is going to be the exact same as yesterday. What we're going to do is take this number and mod it by the K number. So I'm going to talk about how that's going to work and then I'm going to talk about how knowing that cycle detection becomes a very simple consequence of that because once we're always taking this number and modding it by k we realize that the result of that can only be uh somewhere between 0 to k minus one. So roughly proportional to k. So that if we were going to do something like cycle detection, we'd only need to know about all of these possibilities and whether we've seen any of them or not. The risk with doing this is that if there wasn't a solution to it, we'd end up just going on forever and ever. But now that risk has potentially been mitigated. So first recognize that we're always going to start with one and then to get the next number, we're just going to multiply this by 10. Or you could even think of it as like shifting this to the left by one and then adding a one over here. But we're not doing this in binary, so you can't just use the bit shift operator. But you can do the multiply by 10 operator and then you add the one here. And then if you want to do the same thing, you multiply this by 10 and add one. So let's just go through one of these. I guess the most interesting example we have here and see what happens. So we have k= 3. We're going to start with just one. We're going to see is 1 divisible by three. It's not. So, what we're going to do, multiply by 10 and add one. Now, we have 11. We're going to do the same thing here. Mod this by 3 and we're going to get two. And then we're going to do the next thing. We're going to multiply that by 10 and add one. I guess I'll show you the history. So, one mod 3 was originally one. Okay. But now we have this one. We mod this by three and we get zero because it is divisible by three. But I guess the natural question to ask would be do we actually need the entire number every single time? Can we somehow use the result of the previous calculation and still doing like the update the x* 10 + 1 and can that allow us to calculate the mod? And if we can do that, it wouldn't really make much of a difference here because we found the solution in just three ones. But for other examples where we might potentially overflow, that would save us a lot if we can kind of guarantee that the number the this number over here is always going to be proportional to K. And not only is that going to save us from overflowing, it's also going to help us with cycle detection as I mentioned earlier. So, let me just kind of show you intuitively why that does work. And the math is pretty similar to yesterday's math where remember where we said okay if n some number n is divisible we were using five in that case but really you could use any variable let's just say x if n modded by x is equal to zero surely you would agree with me when I say that if I take this number and multiply it by two it's still going to be divisible by x right intuitively I think that makes enough sense. I don't have to bring out the algebra proof. Obviously, if that's the case, the same thing is going to be true with 10, right? 10 * n. But it's not really going to be true or not necessarily going to be true with 10 * n + 1, right? Just because n was divisible by x doesn't mean this is going to be divisible by x, right? And you can even just go through a quick example to figure that out. Like you can use the number itself. If you like for X and N, you can pick the same number. Let's just pick three. 3D 3. Okay, that's true. But then when you get to here, you get 90 + 1. That's not divisible by 3. So clearly that's not going to work. So where am I getting at? Well, I'm getting at is we can separate these. Before I even get into variables, let me just show you the example because I think the example just makes so much sense and it'll probably clear up any confusion that you have. when we have 11 modded by 3 and we get 2 as the remainder. And then the next one is taking this taking every one of these and multiplying it by 10. So 10 * 10 that's going to be 100. 1 * 10 that's going to be 10. And then we also do the + 1. I could also take this entire formula and multiply it by 10. Basically, what I'm saying is if I took this number and multiplied it by 10. So, if I put uh a zero over here, and I know the drawing is kind of poor at this point, but if I put this zero over here, and I put a zero over here, then I get a zero over here. And the math of that is kind of trivial because we're saying like 11 we can say minus3 minus3 minus3 three times that's min -9 over here and then you're going to get two left over. So intuitively like this if I multiply both sides by 10 like it's just a basic algebra property right you you get the zero here 0 0 0 and zero so that makes sense and why am I even doing this why did I multiply it by 10 because we know we're going to take the original number and then multiply it by 10 to bring it here but we're also going to do the plus one so that's what exactly what we're going to do here we're not just going to multiply the result that we got by 10. We're also going to do a plus one. That's going to bring us to 21. So why did I do this math? Because we don't need to take this multiply by 10 and add 1. Because what we can say is we already learned that 11 - 3 - 3 - 3 is equal to 2. So to take this entire thing and do a similar mod operator would be repeated work because when we learned the 11us 3 thing, we also learned that 110 - 30 - 30 - 30 is 20. So no need to repeat this work. But the only difference is we're also going to add one cuz we're also going to add one to this side. So in other words, when we did this, when we get to 111, we don't need to repeat the work, which was the original like -30 -30 -30. And so when you take that away, you get 21 left over. All of this is to say that the math is consistent. We're just trying to eliminate repeated work. You probably didn't need to like go through all this math analysis to just intuitively know this, but now you do intuitively. Now you kind of know the reasoning behind this. And maybe this will be part of your intuition next time. I personally when I was solving this problem, I didn't go through all this math. I just figured I just did this on the spot right now. In my head, just the idea was that this number is of course going to be bigger than it needs to be if you modded the previous number cuz everything with mod always is remainders. We're always thinking in terms of the remainders. So, okay, now we know this and now we kind of know that as we get into bigger and bigger numbers, the algorithm uh is going to look actually like this. So, we're going to have 1 modded by three, we would have gotten one. Then we would have taken that, multiplied it by 10 and added one. So, so far it's equivalent. We have 11 modded by 3 and then you get two. Take this, multiply it by 10, add one, you get 21, mod that by three and then you get zero. So it's easier to mod 21 by 3 than this big number. This is a small difference, but you can imagine once the numbers get really really big, it would definitely make a significant difference. Okay. So once you know that you you realize that in the worst case, a number modded by three, we're always going to get some number that is less than or equal to K. Let's just say it's equal to K. And so if you take K multiply by 10, you get 10 * K + 1. So we guarantee that whatever number that we're currently modding, it's always going to fit in this constraint. It's always going to be less than this, I believe. So once you know that and you know that K is going to be proportional or in the worst case going to be 10 to the^ of five then we're allowed to do what I called the cycle detection because we don't have to worry about like a really big memory constraint should be fine to store these numbers in memory this many. So then every time we get a remainder that's going to represent our new value or at least that's going to be used to compute our new value. So if we ever find that that number is duplicated, we saw it twice. Well, that means that we're stuck in an infinite loop. So if you can't visualize that, just think of it like this. Like you have some number A, then you get to some number B, and it just keeps going. It just keeps going. Maybe for a really long time it keeps going, but eventually you end up at the same number. I won't even draw it this way. I'll just draw it this way. We have an A. Well, we know that math is is consistent. Arithmetic shouldn't lead us to different outcomes. So, what do you think is going to come after A? It's going to be B and it's going to be C and then it's going to be D and what's going to come after D? It's going to be back to A. So, it's going to get stuck in an infinite loop. That's how we are going to solve this problem. So, I believe the space complexity of course is going to be proportional to K. But actually I think even the memory or sorry the time complexity is also going to be proportional to K because we're only going to get K different possibilities that we can try to mod. Okay. So now let's try to code it up. So I'm going to start with our current number which initially is going to be one. I'm going to have my result which is going to count how many numbers we've gone through because now the current number alone can't tell us. Originally the current number uh like it's going to look something like this, right? We know we're not actually going to be storing that number. So we're going to have to use a separate counter which I'm going to call the result. And that's what we're going to end up returning. We're going to iterate while the current number modded by K is non zero. And we're also going to have a hash set which is the best data structure to use constant inserts and lookups. And initially it's going to be empty. And so here we're going to say okay if curr modded by k is non zero. Well let's first check if curr has already been seen. If it's in the previous hash set then we can say let's return negative 1. We've seen this number before otherwise we will add it to the hash set. And uh after that we're going to do the math that I talked about. So then we're going to update cur by setting it to a cur. Well, we do have to still multiply it by 10. Or I guess the order that we do it in doesn't really matter. We can mod this first. Multiply that by 10 and then add one here. So that's what I'm going to do. And then last thing, don't forget to update your result because that should tell us how many digits cur should actually have. So there you go. And let's go ahead and run this. And so you can see here it works and it is pretty efficient. But maybe we can do better on the memory side. So there is a way to actually reduce the space complexity if we did not have this hash set. So I'll just comment it out. What would we do? Because like I said, we know that in the worst case, the size of the hash set could be of size K. So that means in the worst case, our loop is going to run K times. Probably less than that. Like I'm almost 100% sure that the cycle would be less than K in the vast majority of cases. But either way, like that's the worst case. So as long as we handle that, we should be good. So rather than having an early termination, we can actually just time out this loop by hard coding like the number of iterations. just like basically we're setting a timeout on this at least conceptually. So that's what I'm going to do. So we're done with this. We don't have that. So uh we're getting rid of this. And most importantly here, we're going to hardcode this. We're going to say for underscore in range let's say k. So it's going to go from zero to k minus one. And instead of having that early termination by checking the hash set, we're going to take that condition that we had for the while loop and then move it here. We're going to say if uh cur is equal to zero or if sorry if curr modded by k is equal to zero then we're going to return the result. result is still tracking the number of digits. And in fact I think actually we don't even need result anymore because if you look at result it's just an iterator going by one. So I kind of confused myself. I we can definitely oversimplify this. So I can take the place of result. So it's already being incremented. Um but we want this to start at one. So let's actually do that. Let's start it at one. And then for this we'll go up until K + 1. And then here we can return I. So on the first iteration of the loop, suppose if K was one, then we would get cured by 1, which would be zero. And then we would return one as the correct value cuz the curve would have one digit at that point. So I believe this should work and the rest of this well we should get rid of that. Forgot about that. But the rest of this I believe should work. We also have to update this. So I'm getting a little sloppy. But I think that's pretty much everything. So just for my sanity check, let's just confirm that this is doing what it should. The operation is the same. So if I took this turn it into 11, let's say K is 3, then this should be 2. Multiply that by 10 + 1. Yep, we get 21. And then we would check is 21 divisible by three it is. And I believe that would be on the third iteration because for the first iteration, this was 1. For the second iteration, this would have been 11. For the third iteration, it would have been 21. So I think we're good. And yes, you can see it works and the memory is definitely more efficient at the very least. Time complexity, I guess, in some cases, I mean, it's going to be worse actually, I would think, not including like the overhead of the hash set operations. This is always going to run unless we return early. If if the answer is negative one, this is going to run too many times compared to the previous solution. But anyways, thanks for watching. Check out neat code.io for a lot more. I'll see you guys soon.