Calculate Money in Leetcode Bank - Leetcode 1716 - Python

Key Takeaways

hey everyone welcome back and let's write some more n code today so today let's solve the problem calculate money in leak code Bank this problem is easy enough that I think the first solution that I'm going to show doesn't really require a drawing explanation so let's just jump into this problem basically the premise is that we're saving money in a bank starting on Monday we deposit $1 and then every day after that for that week we will deposit one extra dollar so think of it like this the first day we deposit one next we do two next we do three next we do four next we do five six and seven so that's week one now for week two we will start at two and then this pretty much the same rule applies every day after that is going to be one more so two then 3 4 5 6 and a 7 8 and it basically continues like this now the only parameter here that we're given is the number of of days and we are told to return the total amount of money that will be saved by the end of that day so if we had 14 days we would have this much money uh saved up we would total these up by the way this first week is going to total up to 28 do you happen to notice a pattern of how much more the next week is going to be well just mathematically if each day is just one more than the previous day it's probably just going to be the above Plus plus 7 so 28 + 7 this is kind of hinting at the more optimal solution but just focusing on The Brute Force solution AKA like the simulation just going day by day and totaling up the money we can uh solve this problem that way as well so that's like the easiest way to solve this problem so let's actually start with that solution let's just code it up it's pretty self-explanatory at least how we are going to solve the problem in terms of like what code like which variables and stuff it can be a little bit confusing but we know that we're going to start at the beginning let's say we are starting at Day Zero you could start at day one if you wanted to but the math just works out a little bit easier with zero in my opinion I'm also going to have a variable which tells us how much we are going to deposit on the current day and we know on the first day we're going to deposit one and I'm also just going to have a variable for the overall result this is the total money that we're going to have saved and that's also what we're just going to be returning so now we have the setup how do we Loop how do we know how long we should be looping for well basically it's based on the day right so like if the current day let's say is less than n we are going to continue so we want to Loop n times in other words one for each day and on the particular day we're going to save a certain amount and that is going to be known by like this variable what deposit is on the first day it's pretty straightforward it's just going to be one and we know that on the next day it's going to be one more than the previous day so before we go to the next iteration of the loop let's also remember to increment the deposit variable by one and since we definitely don't want to get stuck in an infinite Loop we probably should also increment this day variable so let's do that as well we're pretty much almost done now with this problem but there's one little thing that you might be forgetting and you're probably not forgetting it but I am susceptible to forgetting it think about this we know we're going to be incrementing one more than the previous day but at some point it does need to sort of reset right like eventually we'll get to the seventh day and then we're going to kind of reset back to two here we would get to eight and then after that on the third week we would reset back down to three and uh continue from there like here we would be at four then five etc etc in other words the the first deposit amount for a particular week like the third week is always going to be three the second week it's going to be two for the fourth week it would be four so we know the initial deposit amount like the first day of the week is going to deposit whatever that week number happens to be how can we get that well firstly we know that we are at the beginning of a week like we know every 7 days we're going to need to reset this so we're going to have an if statement down here we're going to say if day moded by 7 is equal to zero then we are at the beginning of a week so this is kind of why I chose day to start at zero though you probably could have made it start at 1 and then just I think had the if statement probably go before this part of the code with this every 7 days we're going to reset the deposit amount and how are we going to do that well it's going to be whatever the current week happens to be we can get that by taking the day number and actually dividing it it by seven and so this will tell us the week number minus one like for the first 7 days this would evaluate to zero for the next 7 days this would evaluate to one so all we need to do is just take this and add one to it that will tell us the week index starting from one like this is week one this is week two this is week three that's pretty much the entire code let's run it to make sure that it works and as you can see it does it's definitely not the most efficient solution though we can do better and for that we're going to head to the drawing board let me give you a very quick math lesson that you might not know if you take a set of numbers like this 1 2 3 4 5 6 and you wanted to sum up a large set of numbers it's actually very easy to do it there is a very simple formula I think it's called gauss's formula I know it from other leak code problems and I knew it before that as well but it's definitely neat I would say the idea is simple notice that we can form pairs of values notice how this pair of values evaluates to 7 1 + 6 and when we go to the right here we're looking at two two is one more than one and from here when we go to the left we're looking at five which is one less than six so therefore the sum of these two numbers should also be seven and it is and same here these two numbers added together should also be seven and they are so this set of numbers is going to be 7 + 7 + 7 what's the math formula for that well you take the smallest number and the largest number of this set of values let's call it low plus High you take those numbers and you multiply it the summation of this multiply it by the length of this set let's call that n divided by two because that's how many pairs we can form if we have n values we can form n / two pairs the formula is going to be this plugging the numbers in we'd get something like 1 + 6 * 6 / 2 which is going to be 7 * 3 that's the formula now does it work if we have an odd value as well or an odd number of values if we had a seven over here it kind of does because we're going to take uh these and these and these as well and then we'll have one left over and that middle value will always be halfway between the sum of pairs and the reason this works by the way is because this set of values is continuous like each one is increasing by one that's why this works just keep that in mind so if we were to apply our formula here we would get I think 1 + 7 that's going to be 8 multiplied by how many values we have 7 / 2 that's going to be 8 * 3.5 which is going to be 28 and that's exactly what we would get from adding these up and actually the offset specifically is what I mean by continuous so the offset between all of these values is exactly one and that's why like the pairs end up adding up to the same value how can we take this math lesson and apply it to the current problem well if you remember the first week week one is always going to be 28 week two is always going to be seven more than that week three is always going to be seven more than that so 42 so we can kind of try to aggregate it based on the weeks this is kind of a shortcut we could take so instead of iterating over the number of days we could iterate over the number of weeks which would kind of cut down the work that we're doing by seven but we can go a little bit further than that we can take this and turn it into a math formula so if we're given something like n = 30 like Nal 30 days how can we solve this problem well we know let me also fill out week four here so we would get that plus 7 so 49 what we want to know is how many weeks do we have in 30 days that's the first step here of trying to apply gauss's formula to this so how we would do that is by taking n Inger division by seven and we would get four four weeks and we'd also want to do probably n modded by seven and then we'd say we have two days left over that makes sense because with four weeks you have 28 days 2 days are left over from those 30 days okay but now let's focus on the number of weeks that we have here four weeks how much money can we deposit in 4 weeks is there a quick way we can mathematically do this yes there is because we know that we're going to take the number from week one up until week four add those two together and that total between those two numbers is going to be the same as this total as well so knowing that we can say Okay first just compute this total whatever it happens to be and then multiply that by the set of weeks which again is four and divide that by two because we have that many pairs we have half those pairs now that's only going to tell us the total of the first four full weeks but what about the last two days we kind of still need to do that and it's okay for us to do that manually because we know there's never going to be more than 7 days left over so it's not bad it still means that we can solve this problem more efficiently the original solution where we were brute forcing the simulation that was an O of n solution cuz we had to Loop that many times but this solution that we're doing doing we're going to have to Loop only up to seven times actually I think it's going to be six and that is constant so this is kind of explaining why we can get away with this solution now in terms of how we're actually going to calculate this getting this number is easy 28 how would we get this number at week four well we would just take the number from 28 the original plus the number of weeks minus one and take that and multip mly it by seven because remember we're adding seven each week so that's why this is the formula for the high number here okay so now let's code this up so the first thing I'm going to do is just take the number of weeks and compute it by taking the number of days and dividing that by seven integer Division and then we can initialize our result and this time instead of initializing it to zero we're actually just going to compute from the First full weeks we're going to initialize the result that way and that will kind of give us a shortcut now if you recall the formula was this I'll actually try to break it down into variables we know low is going to be week one which is going to be 28 and we know high is going to be the last week which is going to be 28 + 7 * the number of weeks minus one and with these two we can take them low plus High we know this is what one pair is how many pairs do we have though we have the number of weeks divided by two That's How many pairs we have now this could actually be an odd number so we can do this as like decimal Division and then we could convert this into an integer if we wanted to but I think another way would just be to rewrite this so I think if I take like the weeks here and just rearrange this like algebraically multiply that here and then divide all of this by two with integer division we should end up with an integer and it's still technically the same math formula that's our result like the shortcut that we took but we know we still might have a few days left and how many times will we have to Loop for that well it'll just be n moded by a seven however many days remain and using that we can compute the rest of the days but for us to do that we have to know what the first day is it would be I plus whatever that first day is of that week and we know that's going to be determined by the week number so if that were week five we would be adding five how do we know which week it is well we actually calculated that earlier thankfully but this was the number of full week so if we had four full weeks and now we're starting on the fifth week we would he say weeks + one so if we wanted to refactor this we could cut this here and make another variable and here call it Monday and then just start at Monday if this is more readable for you and the reason of course that we have i+ here is because each day we're adding one more this is the entire code I believe let's run it to make sure that it works and as you can see on the left yes it does and it's more efficient but the run times are kind of random I ran it several times and sometimes it was more efficient and sometimes it wasn't that's just the nature of leak code but if you found this helpful please like And subscribe if you're preparing for coding interviews check out NE code. thanks for watching and I'll see you soon