Add to Array-Form of Integer - Leetcode 989 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem add to array form of integer so we're given the array form of an integer num for example the number 1200 would be represented in an array like this this is the array form of that integer each digit is going to get its own position in the array so the most significant digit is going to be all the way to the left the least significant digit is going to be all the way to the right in our array we're also given an integer K in this example let's say it's 34 and we want to take this integer K and add it to the array form of this and then return the new array that would be the result so in this case when you add 34 to 1200 we get the integer 12 34. then this in in Array form will look like this 12 3 4. and then that's exactly what we would return so there's multiple ways to do this we're going to be focusing on the most efficient way and even then there are multiple ways to do it the most obvious would be just to take the array and then convert it to an integer and then add K to it because then we don't even have to worry about this being an array we can just add two integers together then get the new integer which would be 12 34 and then take this and convert it to an array that's not too difficult but we're going to be doing it a bit differently we're just going to do it in place because I think it's more interesting so with something like 34 we would want to start at the least significant position and with this integer the least significant position here which is the four then we want to take these digits and add them together we get four and then we want to put that 4 in this position so now we're going to have a 4 here then we're going to take this pointer and increment it to be over here now in the next position over here you could say we want to increment the pointer but an even easier way would be since we're never going to need this digit we could just chop it off how do you chop off a digit well with 34 we can divide it by 10 and round down we would get a 3. we'd basically be getting rid of this digit every time you divide by 10 and round down so that's integer Division and python we need two slashes but I'll leave it like this so instead of Shifting this pointer we're just going to get rid of this and then by default we'll be at the first integer again and now we're going to do pretty much the same thing we're going to take this and divide it or mod it by 10. that's how we're getting the least significant digit anyway when we take 34 and we mod it by 10. that's how we're getting this digit so we would get four we're dividing by 10 and getting the remainder this is a pretty important bit operation well I wouldn't call it a bit off operation but an integer operation and now instead of having 34 we just have three modded by 10 which is going to give us a 3 in the output so 3 is the digit that we want to now add to this position so we'll be replacing this with a three and now we're done this is our solution and we can return it and this is pretty much how we're going to be solving the problem but we're going to make a couple slight changes here because with this really simple example we didn't go through a few of the edge cases a couple would be what if our K number is even bigger than this number in that case instead of just overwriting some of these positions we might have to actually append to the array we might need to add additional values the way we're doing this what if instead here we had 34 000 well in that case these three zeros wouldn't do anything here this 4 would change this one to a five and then this lasts 3 over here would need to go over here the only problem doing it this way is if we have to add new digits inserting at the beginning of an array is an O of n time operation we don't know how many times we might have to do it if this is a really big integer we might have to do it quite a few times that's not going to be super efficient we can instead take this and actually take the original array and reverse it so it would actually be written like this which is kind of confusing when you're looking at it drawn out it would be drawn like this and then when we need to append the three we would just append it on this side and then afterwards once we've built our entire result then we'll take this array and reverse it again and then we'll get something that looks like this well we'd have the 4000 added here but you get the idea that this is going to be in the correct order by the time we return it but for for an intermediate step we are going to reverse it so that when we append new values we'll be appending to the right side of the array which is normally a constant time operation now the last little trick that you have to worry about is what if we have a carry value we don't with this example but taking this and changing it to be a bit more interesting what if we actually had 3 900 that we're doing well we would take this array and it would look like this when we reverse it we would go digit by digit so we'd take this mod it by 10 to get the zeros Place well the ones place and then we'd add that here well it's still going to be zero then we'd chop off this guy look at the zero here and our pointer would be over here we'd take these and add them together well it's still going to be zero so nothing different here we'll chop this guy off again and now our pointer will be over here we're going to take this 9 and add it to the two well when we do that we get two plus nine which is equal to 11. so 11 is definitely too big to put in this spot so what we're going to do to it is we're going to divide it by 10 because we know in real math there would be a one that goes here and then another one that's going to go in the carry position over here so that's what we do we take the resulting number which is 11 I divide it by 10 and that will give us the real integer that we should put over here now before we actually divide it by 10 we would want to mod it by 10 11 modded by 10 would give us this value which is 1 and that's the value that would actually go in this position 11 divided by 10 is what's going to tell us the carry value in this case both of them are 1. so now we would have a one here our pointer would be over here we would chop this off but I guess what I didn't say is where are we actually going to store that carry we know this one is going to overwrite this but what about the carry we know it should be added over here but should we do that immediately where do we store that before we actually get to this position well the easiest thing here is since we already know this three is going to be added over here we might as well add this one to this value here so we'll add one to it and then we'll get a 4 over here that works because we're continuing this addition until this guy is zero until we've gone through every digit so even if we overflowed this like we added another one or we or this was maybe originally a nine and we added one to it now it would become a ten like if this is nine and we add one to it now it's a 10. it doesn't matter because we're only looking at this digit by digit we're going to look at the zero now and then on the next iteration of the loop we would look at the one so it will work out for us in all cases in this case though it's going to be a 4 so let's consider that case we're taking this 4 adding it here to this one that means this is now going to be a five there's no carry here and we'll chop this guy off we've already gone through our pointer here will now be out of bounds but it's okay if the pointer is out of bounds because what we're deciding on how to stop is this guy over here but now since we've gone through every digit over here we are going to stop we've basically completed the addition here we ended up with 50 100 well we would take this and now reverse it which would be 5100 and is that what we were expecting well we took 1200 and added it with the value here which was 3 900 and yeah that looks right to me 5100 is what we would expect and we did this in O of n time because well I guess o of n could be whatever the upper bound is of how many digits the value num has and how many digits the number K has so now let's go ahead and code this up okay so the first thing I want to do is take our num array and reverse it and I'm going to have a pointer I which is going to tell us the digit that we're at in our num array but that's not going to decide how long we continue our loop we're going to continue while K is non-zero so then we want the digit from K that we're going to add to our num so we just take K and mod it by 10 giving us the remainder will tell us the digit now normally what we would say is at num index I we want to add to it the digit that we just got but we can only do that if our index I is in bounds of the num array so in this case we can do that in the other case if I is too big that means we've gone out of bounds then we want to append to this array that digit that's mainly what we want to do but now don't forget to do some of the updates and also don't forget to keep track of the carry what happens if num of I is too large how do we know if there's a carry well we take this value and divide it by 10 that will tell us the carry if it exists if num of I is less than 10 then this will be zero anyway and this is integer division in Python that's what double slash means here so we have our carry and at that point we should probably also take num of I and mod it by 10 because if it is bigger than 10 then we only want to keep the ones play so for example if num of I is 12 and we mod it by 10 then we're going to get 2. we only want the ones place now if it's less than 10 so if it's 2 and we mod it by 10 it's still going to be two so we're not losing anything that's why we're allowed to do this and we don't have to wrap this in like an if statement or anything like that so this is a required operation now remember what we're doing with that carry we're just going to add it to K so let's go ahead and do that but also remember what if K here was 34 and our carry is equal to one then we don't want this to be 35 because remember we want to chop off the digit we don't want to ever reuse that digit so we want to chop this off and then add the carry so it will result in in this case four so before we add this carry here let's make sure to chop off the ones play so we can do that by dividing K by 10 just like we did kind of over here and then we will add the carry to K also don't forget to increment your eye pointer so up we'll do that I plus equal one and that is pretty much the entire algorithm so now before we can return our num we have to also reverse it so I'll do just like this whoops I did not need to index num here when we're appending to it hopefully you caught that earlier sorry about that but as you can see yes it works then it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neatco.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon