LeetCode Weekly 504 | Solutions by Former LeetCode Contest Coordinator

本站添加: 2026-06-01

[00:00:01]Hey folks.

[00:00:03]Welcome to the up solving session of lead code weekly contest 504.

[00:00:12]I'm Arpa from algorithmic academy and I participated in this contest.

[00:00:19]As you can [snorts] see, I have one I have half an hour remaining.

[00:00:26]And I solve all problems. Let me show you I solve the first problem in 1 minute.

[00:00:33]The second problem in 19 minutes.

[00:00:37]Then the third problem 21 minutes.

[00:00:42]And finally the last problem in 13 minutes.

[00:00:47]I'm going to show you the problems and solutions one by one and also implementation.

[00:00:54]Let's start from the first problem. This problem is simply asks us is simply asking us to find the sum of digits of a number.

[00:01:11]Which can be >> [snorts] >> easily calculated.

[00:01:15]Uh First I set my answer to zero. I go over all characters of this uh number.

[00:01:28]And finally I add this value to the answer.

[00:01:40]As you know this is character zero.

[00:01:44]And this the difference will return the character itself.

[00:01:50]>> [snorts] >> And I will add it to answer and finally return the answer.

[00:01:56]Let's move on.

[00:01:59]>> [snorts] >> The next problem This problem is asking us to find the maximum number of uh items we can obtain.

[00:02:21]So, what we should do here, I mean, at least my solution is DP.

[00:02:30]So, uh for each item, either I'm going to pick or I'm not going to pick.

[00:02:41]And if I'm going to pick, it will have it will come with some copy with some copies, which I named gain.

[00:02:59]So, let's define DP.

[00:03:03]The DPB means that DPB means that if I have this budget, what is the maximum number of items I can buy?

[00:03:23]Uh this is the definition for the DPB.

[00:03:26]So, consider I calculated DPB for the elements uh before the current item, >> [snorts] >> and I want to make the new DP. So, I have some old DP and some new DP.

[00:03:43]I make my new new DP based on old DP.

[00:03:49]Uh Um what I'll do is so maybe I'm not going to use this item at all, so DPB will be equal to old B.

[00:04:03]Or I'm going to use it.

[00:04:05]And it matters how many times I'm going to use it.

[00:04:10]Because if I use this item several times, it will yeah.

[00:04:18]So let me write like this.

[00:04:25]DPB is maximum of old B and old B minus item Oh, no, sorry. Let's say price.

[00:04:55]price Uh >> [snorts] >> B minus price plus plus gain.

[00:05:09]Okay.

[00:05:11]plus K Gain is how many multiples this item has in the entire array and it includes itself.

[00:05:28]It includes itself, too, okay?

[00:05:30]So gain will be something like this.

[00:05:36]And DP of B minus price plus one.

[00:05:47]Why?

[00:05:49]Because I could I can use this item several times. So, this is for handling that case.

[00:06:00]Let me show you.

[00:06:05]Okay, I start this uh some empty DP. I go over all items.

[00:06:14]Uh I make the old I define gain.

[00:06:20]>> [snorts] >> I go over all items.

[00:06:23]If this item is divisible by if that item is divisible by this item, I'll add one to gain.

[00:06:33]I'll go over all these different budgets.

[00:06:37]>> [snorts] >> First of all, DPB is maximum of DPB and DPB minus one.

[00:06:42]If I can have uh one money less, one budget less, so that's okay, too.

[00:06:52]Then, if I can purchase at least one item from this item, uh DPB will be maximum of DPB old of DP old of B minus item one plus gain or DP of uh B minus item plus one.

[00:07:19]And finally, returning DP of budgets.

[00:07:23]Great. Let's move on to the next problem.

[00:07:28]Uh This problem is a bit different.

[00:07:37]In this problem, there are some package you can buy that they'll give you two copies.

[00:07:48]And some other package you can buy and just gain one copy.

[00:07:57]Okay, so I'll start with picking some options that give me two copies.

[00:08:06]Like I'll pick them and pick them and pick them.

[00:08:12]And finally I'll I'll start picking some options that will give me just one item, okay?

[00:08:24]So, first let's calculate minimum price over all prices.

[00:08:35]Which is going to show us that when I want I reach the point that I'm going to um choose just items to gain one copy, what is the minimum price?

[00:08:56]>> [snorts] >> Okay, let's put that aside. Let's make my package that I can gain two items by picking them.

[00:09:08]Okay.

[00:09:11]Uh Those packages >> [snorts] >> are coming from an item and its multiple.

[00:09:26]So, for each item let's calculate how many multiples this item has.

[00:09:38]Then we that, I can find how many packages I can make using this item. Like, if this item has three other items that they are multiples of this, I can make three packages using this item that buying each of them costs like this item, but gives me two copies, because I have this and also that.

[00:10:17]And how I can do that?

[00:10:21]Uh, let's see how I can do that.

[00:10:27]Okay.

[00:10:27]So, I define a function that gives me divisors of a number.

[00:10:34]And I cache the answers to make sure uh, I'm not going to calculating this two I mean, two times.

[00:10:48]By the way, I think that the this can be solved even without this.

[00:10:58]Let's try.

[00:11:04]Um, yeah.

[00:11:06]Yeah, even with without that, it can be solved.

[00:11:10]Okay.

[00:11:12]So, this function gives me divisors of number X. That's it, okay?

[00:11:19]Okay.

[00:11:20]So, I'll go over all divisors of this item, and I'll add one to multiples of this number, this divi- this divisor.

[00:11:38]Okay?

[00:11:41]And also I update my mean price.

[00:11:44]Then I have a vector of options.

[00:11:47]These options are pairs.

[00:11:50]The first one shows The first one shows the price for this item. The second one shows how many packages of this price I have.

[00:12:08]Then what I'm what I'm going to what I what I'm going to do is Mhm.

[00:12:21]Maybe this is a better implementation.

[00:12:34]Mhm?

[00:12:36]Seems a bit neater.

[00:12:45]Yeah.

[00:12:46]Let's up Let's get Oh.

[00:12:56]Oh.

[00:13:00]It goes to long long and what it was, so >> [snorts] >> I don't prefer that.

[00:13:08]Okay?

[00:13:09]And let's continue as what we were what we are doing. Okay?

[00:13:14]Okay.

[00:13:16]So, I have these number of uh options of this price.

[00:13:28]Then I define my answer. My answer is simply budget divided by mean price at the beginning.

[00:13:38]I sort options based on their price because all of them give me just two items. So, why not to sort?

[00:13:46]And current means that how many options I already picked.

[00:13:51]Then I go over all options.

[00:13:54]I can't pick more than budget divided by option for sure.

[00:14:01]Then I do but I decrease the budget by the cost of all copies I want to pick from this option.

[00:14:14]>> [snorts] >> Then I'll set I'll add all them to current.

[00:14:19]And with the remaining of budget, I'll buy those initial uh items with mean price.

[00:14:31]Yeah, that's it. That's it about Q3.

[00:14:34]Let's move on.

[00:14:36]Move on to the next problem.

[00:14:38]Q4.

[00:14:40]Um okay.

[00:14:44]This is actually easier than the last two problems at least for me.

[00:14:50]Um to make the array lexicographically maximal, for sure my choice will be something that comes with max of the entire array.

[00:15:09]Good.

[00:15:12]So, the first element of result is the most important element of result for sure.

[00:15:22]Okay?

[00:15:23]So, I need to maximize it.

[00:15:26]And what is the maximum possible value for the first element of the result?

[00:15:33]That is mex of nums itself.

[00:15:40]Okay. So, I need to calculate mex of result.

[00:15:48]Mhm, sorry. Calculate mex of nums.

[00:15:51]And then find the minimum length prefix of nums that has this mex.

[00:16:03]And then repeat and repeat and repeat.

[00:16:09]Okay.

[00:16:10]To do that, I'll come with some suffix mex, like partial mex.

[00:16:21]Okay, from uh from right to left, from the end.

[00:16:28]Uh I'll come with that.

[00:16:33]Using that, I can calculate I I I can have mex for all the suffixes of all the possible suffixes.

[00:16:46]Then, what I'm going to do is is starting from some point.

[00:16:53]This is And then setting the target for mex.

[00:16:58]Then I go as uh then I go until mex of this subarray is equal to goal.

[00:17:09]I'll add this mex to the answer, to the result.

[00:17:16]Then I start I start all over again.

[00:17:21]Look, like this.

[00:17:24]I define this function which this array which will be equal to suffix mix of I. Mhm, this is pretty easy to maintain. I mark it. While this is marked, I add one to mix. That's it.

[00:17:48]And finally, I reset the array mark. The array mark is global array here.

[00:17:55]Then, I have my answer.

[00:17:57]Now, I go over I, J, and I have my mix.

[00:18:04]If I is equal to J or mix is still less than what I need, I go over Um I I will add this number, number J, and I'll update mix.

[00:18:31]Okay.

[00:18:32]Then, I'll add mix the answer, the current mix the answer, and I'll remove all numbers from mark and restart all over again.

[00:18:45]Yeah. That's it.

[00:18:48]Uh we solve all problems in 20 minutes.

[00:18:52]Um thank you for watching, guys.

[00:18:56]Join us very soon in the next of solving sessions of Codeforces and LeetCode contests. Thank you. Bye-bye.