LeetCode Weekly Contest 504 Editorial + Screencast (slow but steady)

Ajouté : 2026-06-02

[00:00:00]Uh, hi. Uh, this is a video editable for the Elite Code Weekly One 504. I'd say the problems this time were decent. Like Q4 was on the easier end, but I found Q3 quite enjoyable. Q2 was all right as well. So, I'll be going through the problems in the order of that appearance and I'll share how I implemented my solutions. I'll explain my my implementations which I did during the contest. And after this I'll attach the live solve section where you can see how I approach the problems in the live contest itself.

[00:00:31]So Q1 was straightforward as expected since it was a three-pointer.

[00:00:37]Uh basically for for an integer we had this sum defined which was the digit into the frequency of its count overall disting and we have to return the score.

[00:00:49]Right?

[00:00:51]So like this is uh you could either simulate this using a map or something but if you observe this is basically just the sum of all the digits. So instead of doing all this uh we can also do this.

[00:01:09]One second.

[00:01:30]This this would just sum all sum all the dates and return that. So this works for this problem as well and the implementation is way shorter.

[00:01:40]Moving on to Q2. Uh Q2 was like harder than usual Q2 but it was still like if you know some concepts it's straightforward. Basically we are given an array of items where we have the factor and the its price. And now for Q1 the number itself is still 10^ 9. So this will work since that means at most 10 digits. So this is of one of 10 of length log base 10 for q two we have this array items where we have the we have the factor of the item and the price of the item and we have some budget and we have to find the maximum number of items we can buy within this budget. So this is kind of an abs setup, right? But we have for every item we have unlimited copies and like for the first item we buy of every type we can get um free copies and free copies have to follow this rule.

[00:02:39]Basically uh J can be a free copy of I if we are buying I for the first time obviously and the factor uh J is divided by factor I and this was the second point basically this basically re uh restates what I said before that we get free copies only when we buy it the for the first time right and the same item can be uh gotten we can get the same item for free via multiple eyes and the most important thing here were the constraints and the length of the items is less than equal to,000 the budget is less than equal to 1500 right so basically like we can do some sort of knapsack here on this n cross budget but how do we handle the free items thing so what I did was uh let's say we are at some index I with some budget remaining x right either Whether we buy I or we don't buy I that would be the regular knapsack. Right? So if we buy I we go to I + 1 comma X - Y where let Y be the cost of I. Right? If you don't buy I we go to I + 1 X. Right?

[00:03:53]Since we didn't buy the budget remains the same. One second.

[00:04:00]But here uh but here we can we have unlimited copies of highlight. So we can buy multiple of them. So instead of running a loop which can increase our complexity, what we can do is if we don't buy I, we just don't buy it, right? So we go to I + 1 X. But if we buy I, what we do is uh we transition to I comma one second I comma X minus Y. This basically means that we have bought one copy of I and we are still staying at I to see if we can buy more eyes. Like if we buy more I we be here only else we transition to here.

[00:04:33]You can think of it like a sort of graph, right? So this graph would be like this. We are at some this point either we buy it again.

[00:04:42]So we loop back to here but with lesser budget which [clears throat] since we have bought it one more time, right? Or we go to the next node. So this will work like this.

[00:04:53]But now we also have to keep a track since if we if we are buying something for the first time, we get free extra copies, right? So we can keep another index here like let's say F which stands for if we bought it for the first time.

[00:05:06]So if we are transitioning to I + 1 the F value would be zero as well. But if we do this transition the F value would always be one. And using this F value we know if we want to if we are buying it for the first time or not. And if we are buying it for the first time we can uh add the extra free copies. And since n is less than equal to,000 we can uh compute the free copies using a brute force only. So this is my solution.

[00:05:32]Basically this is me just resetting the db matrix. This is extra which states how many extra copies of uh I how many extra copies of J I get with some I computation and this is the recursive call.

[00:05:49]So here uh either we don't buy it. If we don't buy it uh that means we haven't bought it before this is always zero I + 1 and same budget else if we can buy it we transition to since we have bought it one time we do this plus one since we have bought it this is always one and then budget minus items I remove the cost of that and if we haven't if we haven't bought it before then we also add the extra ones here and yeah this was the DP I I had some implementation mistakes which is why it took me slightly longer than it should have like I had this idea fairly quickly but implementation mistakes were a theme this contest. So this was Q2. Q3 has kind of the same setup but the difference is we have this uh budget and price are less than equal to 10^ 9 factors are less than equal to 10^ 5 only n actually but and there was also one like I I usually for these like two-parter problems I usually solve them together. But here there was some other different difference as well.

[00:07:15]I think it's likely the same. Okay. So, we'll see. I'll see any differences if there are any. First of all, the obvious difference is in the constraints, right?

[00:07:28]But I want to see if if this would pass here.

[00:07:43]Yeah. Okay. So there there's some other difference in the problem.

[00:07:50]All right. Never mind. So uh going through the problem statement again we have unlimited copies the items and the budget that remains the same. But we have this for every purchase copy of I.

[00:08:01]It can give me at most one free copy of another J. It does not give a the difference only.

[00:08:11]We receive one free copy of every J right such that this rule is followed here with every I we only get one free copy of J. So this is how the problems are different and the satisfiability should be the same only such that uh it is divis factor I J is divisible by factor I and this every ordered pair can exist only one but the same item can be received from different I right obviously we can't DP here since we have this the the constraints won't fit for the budget into anything but we can make some observations s here.

[00:08:50]First of all, uh we only have to maximize the count, right? So let's say we have if the if there were no free things, we had two items. One was let's say of some cost five and one was let's some cost three and we had some budget let's say X. It's obviously better to buy the cheaper one since XY3 is always greater than equal to XY5.

[00:09:14]This would be equal to because of some float shenanigans but usually this is the case right. So here this buying this will always be better. So like once once we have exhausted all of our free items buying things we can try using this idea right. So now we have to think about how do we exhaust the free items.

[00:09:36]So for the free items uh my thing was let's say I have some price uh p I price I of some item I with some factor I right this factor I allows [snorts] us to buy some at most K more items my bad let's say this factor I allows us to buy some ko items right the different ones so for these k items uh this is basically Since we are getting these for free, it basically means that we are buying two items at once. So, we'll have some pi. We'll have one second. We'll have some I with some uh uh one second.

[00:10:17]Let me visualize this better. We'll have I with plus this, I plus this, I plus this and I plus this. This means for these items in if we are buying four, we are actually getting eight, right?

[00:10:32]So this this thing was a idea which I had uh so for this uh let's say like somehow we can get this count very quickly.

[00:10:46]We'll see how we'll calculate this later but let's say we can get this count very quickly.

[00:10:51]So I have some and I have some budget uh x let's say x remaining.

[00:10:57]Now I can buy uh budget. If I'm buying this for the first time, like I'm trying to exhaust all of the items for the first time, right? I can obviously uh buy an uh it's 1 second. Its cost would be BI. The cost of the current item is PI.

[00:11:21]Now PI, right? Yeah, PI is already the cost.

[00:11:24]So I can buy uh x is the budget right my bad. I can buy XYPI items that that is already an upper bound right on the number of items I can buy and even with this upper bound how many the free ones I can get it is bound by K right so we have min of K comma X by PI these are the items I can get twice of so this would be into two because I'll get X and I'll get I'll get the PI itself and the once I'm for free. So this would be the case and since here I'm getting two items instead of one the cost for every item would be pi by 28 instead of pi.

[00:12:11]So and here I can basically so my idea was for every item it would exist in a pi state and a pi by2 state. I'll sort based on these. I'll get the lower one first the small since let's say this pi was let's say some 100 or something and we already have some item which we can buy for five. So it's always already better to buy that right. So what I did was I sorted every item based on pi and pi by two and I went from the end uh basically I went from the best one I I checked if it was of type one or type zero. Type one is basically uh it refers to the fact that we are doing this this operation the one where we are getting other items for free as well and type zero is the one where we have already exhausted this operation so we have to do this. So after sorting it was just doing this math and adding stuff. So this was my implementation and yeah one more thing for getting this count I stated we are uh I stated we have to get this count right for this count we can use the harmonic sums idea where first we mark every frequent factor frequency and then for every factor we create some other area let's say h in which we do the harmonic sums iteration. So here uh max f is the max possible factor value. h has the harmonic sums value of frequencies.

[00:13:36]Right? So here I'm doing this but this will also include the value of itself.

[00:13:40]So here in the calculation I'll subtract it by one.

[00:13:44]Here I'm creating the array by adding both zero and one. Zero is the state where we have already bought it and one is the state where we are buying it for the first time which means we are doing this operation.

[00:13:57]And then this is just the sorting logic.

[00:14:02]I'm I actually I traded it. I sorted it in the reverse direction. So I can do this pop back thing. I get the index and the type. I get the factor and the what is this?

[00:14:13]The price. Yeah. If it's type one then we do this extra possible thing. Is this only this min of budget by cost and the extra possible here I'm subtracting by one because it will include itself as well. So we have to remove that to get this. And then we do this.

[00:14:32]We are adding two into count since obviously this will fetch us one free one.

[00:14:40]Else it is uh and we subtract them from the budget. Else this is the other variation where we can buy multiples uh where we have already bought stuff.

[00:14:49]So we can only do a simple buying operation which fs one. So it is just this and at the end I'm just resetting my frequency and harmonic comes out.

[00:14:57]So this was Q3. I like usual harder than the usual Q3 but I like this problem.

[00:15:04]And Q4 was it's kind of interesting.

[00:15:09]Basically we are given an array nums and we want to reconstruct array result by repeatly performing the following operation. Like we choose a integer K such that K is between one to the remaining length. We compute the max of the first K. We append max result and we remove the first here now we have to return the lexographically lexographically largest result. Right?

[00:15:29]So my first intuition was since we are doing some lexioraphically largest thing we can maybe apply greedy because lexioraphically largest means like if we have two options we can make somehow make this larger. This is the uh result right? This is index zero. This is index one. If we can somehow make a earlier index greater it would mean result that it would mean that the output is less secure graphically larger.

[00:15:56]So this was my idele idea here. If it is possible to make the current max larger I would always do that and if it is not possible it is always optimal to end it early because it would allow us to increase our string size. Right? So if we have some a and let's say some other characters any other a a and here we just have a so this is lexographically larger because it has a larger string right but if we had this is this this for b this would be lexographically larger so this was my implementation idea basically and my implementation just uh supplemented this idea where I kind of simulated this only I for every value since and the constraints obviously were n and x less than equal to 25. If even if x were larger than n, then we could just let's let's say x were less than equal to 1 9. We could ignore values greater than n + 1 because those would never be a part of max anyways, right?

[00:16:55]So in my implementation what I did was I tracked the indices of every value.

[00:17:02]And now since we have to choose k at least one, I'm doing performing the k at least one. I'm setting the current max based on the K right.

[00:17:10]So here this is a set of the current elements I have and this is the current max I have.

[00:17:17]I have to choose K equal to at least one. So I've done that and now if the max if there is some index which has this max I'll set that as my target and I'll go to that index. While going there I'll remove these values since this those will get eventually removed.

[00:17:36]And then after that is operation is done. I'll increase my max and this is repeated while the operation stops. And this even though it seems like it's a triple nested loop here this all of these loops are moving this SD pointer head right. So every SD gets activated upon once and this works and at the end I'm pushing back max to my answer and I'm returning the result.

[00:17:57]So like the explanation of this problem was shorter because this is just like implementation idea right like I want the earliest index I uh actually like this is also not required you can use the vector instead but I'll leave that exercise to you.

[00:18:12]All right so yeah this were these were my solutions for the problems overall I felt the problems were like of nice quality like especially Q3 I liked a lot and after this you can see how I approach these problems in the live contest itself. All right.