Make Sum Divisible by P - Leetcode 1590 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem. Make sum divisible by P. Sorry, I missed the last several days. I actually went to get some milk and there was a really long line at the grocery store, but we're given an array of integers and we're also given a separate parameter called P. The idea is that we want this array to be divisible by P. In other words, if we were to compute the sum of the entire array and then mod it by P, we expect the remainder to be zero. Now, it's possible that the entire array itself is divisible by P, in which case we would return zero because we had to remove zero elements from the input. Otherwise, we have to potentially remove some elements to make the entire thing divisible by P. It's also possible that it's just like not possible for us to do that. in which case we would say return negative one because there is not a valid solution. But when we remove elements, we do so contiguously. You can't like take multiple separate elements that aren't connected. We can only take one contiguous subarray from the input and remove it. We would of course take the remainder, see if it's divisible by P. And we want to remove the smallest possible subarray from the input. There could be multiple solutions. We want to remove the smallest possible subarray. Now, in case there are multiple ways to do that, like maybe remove that or remove this. If there's a tie, it's okay because all we want to do is return the length of the subarray that we have to remove in order to make the rest divisible by P. So, in this first example, it looks like it is just one. If we were to remove this four, we would see that the remainder is 4 + 2. That's 6, which is divisible by 6. Now, what is the brute force solution to this problem? I've more or less summarized it here. As long as you kind of understand these basic facts, it's not too difficult to arrive at a brute force solution. Clearly, we would want to consider every possible subarray and consider removing it from the input. How exactly do we do the math for that? Well, there's going to be roughly n squared subarrays. So, you compute the sum of all of those. If we have a variable that tracks like the total of the input, the total sum, then it's pretty easy for us to just take the total, subtract from it a particular subarray, and then just check if the remainder is divisible by p. We'd find the smallest subarray that we could remove that would satisfy that. And so overall, the time complexity would be n^2. So is it possible for us to do better? Is there a shortcut? Is there any repeated work? Well, this is not an easy problem, but it's actually very similar to a few other problems that we've solved. This problem is similar to a couple others that we've solved before. I think this is probably the easiest version of that problem. Subarray sum equals K. It's not an easy problem by any means, but in case you're looking for like a similar problem, that's one. And then this one here is probably more similar. And we did that like 3 months ago. So, this one's relatively fresh in my mind. And so when you arrive at a problem like this, you want to at least think of what kind of linear approaches do we have to solve something like this. It could be sliding window two pointers, maybe even binary search. Well, prefix sums is one that I've seen used in this context before. So I immediately start thinking of how can we apply prefix sums to this? Would we care about in terms of what's the prefix? What exactly do we want to remove? Well, think of it this way. If we want to be able to solve this in linear time, perhaps we like iterate through this once or twice, but not a variable number of times. So for each element, we kind of need to consider something. And the thing I'm going to be considering is let's just pick like an arbitrary position where here let's try to determine what is the smallest subarray ending at this position that we could remove from the entire thing that would make it divisible by P. So we're going to think of it in terms of sub problems. Originally, we want to know what's the smallest subarray we could remove from the entire array. We're going to break that up into sub problems. We're going to scan through this from left to right. And at each position, we're going to consider what's the smallest subarray ending here that we could remove. And we're doing that deliberately. Like this isn't just something random that I'm making up. We're doing this. We're scanning left to right because by the time we get to this position, we will have seen all the elements that come before it. So, it's valid for us to ask, well, what's the longest subarray ending here that we could remove that would make it valid. We can't predict the future. We can't read elements that we haven't seen before, but we do have access to all of these or at least we've read them. Now, if you do know how the math works in terms of modding by P, you recognize that like let's just kind of draw out the numbers. Consider that we have these sums 1 2 3 drew a bunch of numbers down here. I could keep going, but eventually six is divisible by this. So the remainder is zero. 12 is also divisible by it. So the remainder is zero. With five though the remainder would be five. With 11 the remainder would also be five. So there is a bit of a pattern here. Now if we wanted the entire input array to be divisible by this. What should we do? Well, we should probably compute the entire sum of this. As I kind of mentioned earlier, I think this is 4 + 6. So that's going to be 10. And so we want this number to be divisible by six. So what should we do? Well, all we're allowed to do is remove a subarray. So at this point, I want to just jump into the solution itself because there's going to be a few components to this problem and it's really easy to get confused. So the first thing that I want to establish is that we are going to compute the total sum of this. And then we're going to take that total and mod it by P. And that's going to give us what I'm going to call the remainder or like the target value. So like in our example, if you take like 10 mod it by six, you're going to get four. The reason that this is important is because every time we remove a subarray, we need that subarray to have a remainder of this value because only then will the remaining elements add up to having like a remainder of zero when it's like divided by this. Basically, then the remaining elements will be divisible by this. So we need that to be the case. But remember, as we go through this, we want to try to remove the smallest subarray ending at each element. Part of the reason for that is because if we remove a prefix, we don't necessarily know that the solution is going to be removing a prefix. We have to also try to at least remove elements or subarrays that are in the middle of the input. So that's why we establish the rule that for every element, we're going to consider the longest or rather the shortest subarray ending at this element and consider removing that. So, just to show you how the math is going to work out. Let me like arbitrarily pick uh this position, what we're going to do is we're going to keep track of what the current sum happens to be. So, as we scan from left to right, that's kind of our prefix, our prefix sum at least. So, at this point, it'll be about a right now. Do we actually care about the value itself or do we care about the remainder after it's been divided by six? We mainly care about the remainder. You could also keep track of the total, but just to keep things simple, let's assume that I'm going to have the remainder. So this is eight, but the remainder is obviously going to be two. You mod that by six, you get two. Now what does this two tell us? The remainder of this entire subarray ending here and starting here is two. But we wanted the remainder to actually be four because if it was four, then we could remove that and then say, okay, all the remaining elements are now divisible by P. But it's not. So we need that difference. we need to remove a prefix from this so that the real remainder becomes four. In other words, just to kind of do the quick math, let's say this is our cur. We need to subtract from that like a prefix. Let's call that x. So that what's actually left over is this value, our remainder, or in this context, it's going to be four, but I'll just use the name here. So if we wanted to solve for x here, we would just say well x is going to be we would get cur minus the remainder. So just plugging in the math here, what are we going to get? We're going to get cur, which is 2 minus the remainder, which is four. So this minus that, we're going to get -2. So we need to find a prefix with a sum of -2 to remove. That doesn't really make sense, does it? Let's go back to this number line that I was trying to kind of make. We have one, two. I know this is getting kind of hard to read. So, let me just kind of draw the border here. So, when we were at two, we were actually saying our sum right now is eight, but we want the remainder to be four. So, this is kind of where we want to be. So, in other words, you could think of it as wanting us to remove a prefix of four. In the context here, that does make sense. Right now, our total thing is eight. If we remove this prefix of four, we are left with a subarray that has a sum of four, which is exactly what we want. We want to remove the smallest subarray that has that remainder. Now, the problem here is that when we do this math, since we are concerned with the remainder, we have like the total, which is eight, but we actually converted that into a two. The easiest way to just get rid of like the negatives, this actually will work in Python, but just to kind of make it a bit better, we can just offset this with P. So when we uh do this equation down here, you can just add like a constant plus p, which in this example was six. So therefore, like this thing will actually never be negative because we're always going to take cur and make sure it's modded and the remainder is always going to be less than p anyway. But that's kind of the main intuition behind this problem. That's like the main math. That's the main idea. Now the last thing that you're probably wondering is, well, how do you get those prefixes in the first place? That's something we can very easily store. So we will use a hashmap for that where we will keep taking whatever our current number is and we will map it to the last index that it's been at. So for example, we might get this which has a prefix that's modded which has a mod by once you mod it by p it becomes four. It's kind of why this problem is so hard to explain cuz even just mentioning something small like this requires like two sentences. But anyways, we're going to map that prefix remainder to the last index. So this will occur at index 2. So we have that but we see that same prefix again here ending at index 3 cuz this is 10. 10 modded by p is going to be a four as well. So then later we would replace that and say okay well this mod this prefix remainder which is four instead of being mapped to one now it's actually going to be mapped to three. This way we always remove the longest prefix from the beginning. Again this is a very difficult problem. I'd recommend checking out the other two variations of it which are a bit easier. Okay. So the first thing I'm going to do is just compute the total of nums. We can do that with the sum function. It's built in. And then we're going to compute that remainder that special number. So take the total mod it by p. And there is one edge case that I only realized because my submission failed. If the remainder is exactly equal to zero, in that case we don't need to remove anything from the input num. So we can just say that the length of the subarray we remove is going to be of length zero. Otherwise we are going to try to compute the smallest subarray we have to remove. So initially I could set this to infinity or I could set it just to the length of the input itself. Now one edge case that they mention is that the result is the entire subarray itself. Like we cannot remove anything smaller than the entire subarray. In that case we want to return negative one. So I can handle that in Python with like a little turnary operator like this. Otherwise I can return the result. So now to actually do the computation, I'm going to maintain one variable called current sum. This is kind of like our prefix so far. And then I'm going to iterate over the input. I'm going to need the index and the number itself. So I'm going to use enumerate in Python. And every time we get to a value, we just want to add it to our current sum. So that much is straightforward. We're maintaining what the current sum happens to be. And while we're doing this, we might as well also handle the mod at the same time so that this doesn't get too big. So just mod it by P because what we care about are the remainders anyways. And now remember that math formula that I was kind of talking about. It's hard to reason about when we're dealing with remainders, but it was something like this. The remainder plus X the difference should be equal to the current sum. So if we solve for X, we get something like current sum minus the remainder is what X is. And so this is basically the prefix that we want to remove from our current sum. So that the current sum has a remainder of this. So long story short, we're going to do something like this. The prefix will be equal to current sum minus the remainder. And since this could be negative, we're going to add a p to it plus p. And then we're going to mod the whole thing by p. You might think, well, why are we adding the p and then modding it? Isn't that not going to change the result? In some languages, I think it will. In Python, you'll probably be fine without having this. But in some languages, that will make a difference. But once we have that prefix, this is the prefix that we need to remove from the current subarray to make the current subarray have this as a remainder. So let's check if this already exists. Have we already seen this prefix before? Well, the only way to check that would be by having a hashmap, which I'm going to call remain to index because I'm not very good at naming things. But basically what this is going to do, it is going to map the remainder of the prefix sums to the last index that they occurred at. So down here I'm going to say if this prefix already exists in this hashmap, I want the index that it ended at, which is going to be this remain to index of this prefix. And so now I want to know what's the length of the current subarray after we remove that prefix. Well, that's why I kept track of the index here. So, I'm going to say my current index minus the index that this one ended at is going to give me the length. And then with the length, I'm going to try to minimize the the subarray that we're trying to remove. So, my result, I'm going to try to minimize that. Set it equal to the men of itself and the length. So, now we're almost done. You might have noticed though that we're not actually inserting into this after this if statement, whether it executes or not. We want to say that the last time that we saw this current sum was here. So we're going to say remain to index of current sum is ending at this index I. There's one edge case here that we're missing. What if the first element itself was divisible by P? What's the remaining prefix that we would remove in that case? Well, this if statement would be false because we haven't seen zero yet. So in other words, we want to say that the empty subarray which has a sum of zero is going to be mapped to negative 1 because if we started at like index zero, then we'd say 0 minus this index which would give us a length of one. So it's kind of like our base case. Now this is the entire code. Pretty challenging problem, especially for this early in the month, but you can see it works and it's pretty efficient. Thanks for watching and I'll see you