Minimum Limit of Balls in a Bag - Leetcode 1760 - Python

[@vukanoa]

Okay I've finally understood it, here is my LENGTHY explanation: The problem is that Neet didn't go through the 2nd Example that has more than one Bag at the beginning and it confused most of us. Let me explain my understanding using a few examples. First, even when considering a "Brute Force", you MUST understand what is this range that Neet shows. It is NOT a range for ONLY splitting current number(9 in his case). Instead, it is the maximum possible and the lowest possible MAX value AFTER the split. (This is confusing, keep reading it gets a lot more clear) Let me say that in another way: Example: nums = [7, 5, 9] Current max_value is 9. a) If we performed NO operations, what would be our penalty? It would be 9. b) However, if we had INFINITE amount of operations, we would be able to split each and every bag in "nums" so that every single bag contains only 1 ball. {7} -> {1}, {1}, {1}, {1}, {1}, {1}, {1} {5} -> {1}, {1}, {1}, {1}, {1} {9} -> {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1} So, now we know that the MINIMAL possible result(i.e. penalty) is 1. But to achieve that, for our example: nums=[7,5,9], we'd need: 7 splits + 5 splits + 9 splits == 21 splits We would need maxOperations to be 21 or higher. On the other hand if we had maxOperations == 0, then our MINIMAL possible result(i.e. penalty) would be 9, since that is the largest element in "nums" without any splitting whatsoever. Now we know WHY the range is: [1 ... 9] Let's continue: Now, if we did it in a Brute-Force way, what would that even mean? // This is VERY important! WHAT is each element in this range [1 .. 9] representing EXACTLY? Let's say we pick number 6 from this range. WHAT is 6 representing? WHAT are we trying to do with it? We are trying to see if we can SPLIT all the elements in "nums" in such a way as to have 6 as the maximum value, BUT we MUST do it in maxOperations or LESS. 6 represents the maximal value AFTER optimal splitting maxOperations times. Let me say that again, this is the absolute CRUX of the problem! If we've picked 6, we want to go through each element in "nums" and ask: How many operations is needed to split this ONE bag into TWO OR MORE bags that have have 6 as the biggest amount of balls in those newly created TWO OR MORE bags? nums = [7, 5, 9] {7} --> {3}, {4} // We needed only ONE operation to achieve that {5} --> {5} // This bag is ALREADY less than or equals to 6 {9} --> {3}, {6} // We needed only ONE operation to achieve that or --> {4}, {5} So now we sum amount of operations for each original bag in "nums" needed to create TWO OR MORE bags, per ORIGINAL bag, that do NOT have more than 6 balls per bag. 1 split for 7 0 split for 5 1 split for 9 1 + 0 + 1 = 2 Thus, we conclude: nums=[7, 5, 9] can INDEED be transformed to nums={3,4, 5, 3,6} or nums=[3,4, 5, 4,5] As you can see, AFTER the transformation 6 is the max_value. We can achieve it in maxOperations = 2 or more Since we've seen that we CAN INDEED get bags of 6 or less balls per bag using maxOperations = 2, now we can try the same thing but with 5. But instead of LINEARLY trying: 9, then 8, then 7, etc. We can perform a Binary Search. If we CAN INDEED split it as to have "mid" amount of balls or less per bag in maxOperations, then we consider that a potential result and we shrink the range and try again in hopes of finding a lower "mid" value that can be max_value after the split maxOperation times or less. If not, we shrink the range but to the right and try again. Here is the "Simulation" of a Binary Search on this same example and another explanation of those same concepts in case someone still doesn't understand them. Can we split all the bags in "nums" in maxOperations or LESS so that "mid" value is the maximum number of balls in any single bag? Example: nums = [7, 5, 9], MaxOperations = 2 // We want to make "nums" have "mid" value as its maximum mid = 5; How many operations do we need? 9: How many operations we need in order to split a bag of 9 balls in such way as to have only bags with 5 balls as the biggest amount per bag? The answer is 1. Why? Because we can split a bag of 9 balls into two bags: {9} --> {4}, {5} As you can see, AFTER the split, maximum number of balls in one bag is 5(i.e. our "mid" value) or less. 7: How many operations we need in order to split a bag of 7 balls in such way as to have only bags with 5 balls as the biggest amount per bag? The answer is also 1. Why? Because we can split a bag of 9 balls to two bags: {7} --> {3}, {4} AFTER the split, maximum number of balls in one bag is 4. 5: How many operations we need in order to split 5 balls in such way as to have 5 balls as the biggest amount? The answer is 0. Why? Because we already have a bag of 5 balls, we don't need to split it further. Now we sum the total amount of operations needed to split nums=[7,5,9] in such a way as to make mid=5 the largest value: 1 + 1 + 0 = 2 2

[@itmesneha]

thank you!

[@anithcherianjoy6326]

WOW... great explanation. Thank you

[@steel_hat_pirates]

@@vukanoa you should start blogging man

[@lian1238]

The part that I didn't think about on my own was the math of finding the "number of operations needed to split X so that the max is Y" The part where he used ceiling

[@nirmalnarayanan4073]

Thank you for such detailed dumbed down explanation of this logic!!

[@business_central]

you saved the day, I was stuck after thinking priority queue and then failing, then seeing talk about binary search but I couldn't come up with the right approach. Thanks for the save!

[@anmolkumargupta2528]

HEAP SOLUTION (I was also stucked at heap,this is not my solution, I have seen it in solutions) class Solution: def minimumSize(self, nums: List[int], maxOperations: int) -> int: u = sum(nums) b = maxOperations splits = [max(n*b//u, 1) for n in nums] heap = [(-1 * ((n+split-1)//split), n, split) for n, split in zip(nums, splits)] heapq.heapify(heap) for _ in range(maxOperations + len(nums) - sum(splits)): item = heapq.heappop(heap) _, n, split = item num = (n+split)//(split+1) heapq.heappush(heap, (-num, n, split+1)) return - heap[0][0]

[@moralized]

haha, glad i wasn't the only one who thought priority queue 😅

[@bishwashkumarsah171]

when ever you see maximize and minimize think first about binary search

[@JamesBond-mq7pd]

for those who dont understood: You need to find a number by iterating from 1 to the maximum value in nums, where for each number, the total sum of ceil(x / your_number) - 1 for all x in nums is less than or equal to max_operations.

[@ayushsinha4280]

A similar problem was asked to me at an interview, even thought I have seen similar problems I fumbled. Didn't got the internship.

[@33galactus]

Here the key is knowing the intuition of the problem, i.e. why are we doing this. Once we understand it, implementation is trivial. For those who did not understand, let me share my perspective. First part is "Understanding the Range of Answers". If no operations are performed, the largest number in nums (i.e max(nums)) is the answer. Example: nums = [9, 5, 7], no operations → answer = 9. If we could perform unlimited operations, we could split all values into 1, making the answer 1. Example: Split all values repeatedly → answer = 1. Thus, the possible range for the answer is from 1 to max(nums).

[@33galactus]

Second part is "Exploring the Range of Answers" We can think of the relationship between the "maximum number of balls in any bag" (the answer we're trying to find) and the "number of operations required." For a given maximum value (max_value), we can calculate how many operations are needed to split each number in nums so that no value exceeds max_value. 1. If the total operations required ≤ k, then max_value is valid. 2. If the total operations exceed k, then max_value is too small. Start from max_value = 1 and go up to max(nums). For each max_value, calculate the required operations (can_divide(max_value)) and check if it is within the allowed limit (k). The first valid max_value is our answer.

[@33galactus]

This was the intuition behind the problem. Now, let’s move on to the last part: "binary search" to further optimize the solution. Instead of checking every possible value, we can use binary search to efficiently narrow down the range of potential answers. Once the intuition is clear, transitioning from a linear search to binary search becomes trivial. That’s my two cents - hope it’s clearer now. Thanks a lot Navdeep for your efforts and video !

[@aaditya3360]

The approach is not clear for when there is more than 1 entry/number in the input array.

[@JamesBond-mq7pd]

You need to find a number by iterating from 1 to the maximum value in nums, where for each number, the total sum of ceil(x / your_number) - 1 for all x in nums is less than or equal to max_operations.

[@mirkelor]

we can also use (x - 1)/y ('/': integer division); ceil(x / y) = (x + y - 1)/y, ceil(x/y)-1 = (x + y - 1 - y)/y = (x - 1) / y

[@trueinviso1]

Coming up with the math behind this doesn't really make sense.

[@oppie335]

Totally agreed

[@marcoaraujo9446]

Neet Do AdventOfCode Lives, would be nice to see u solving these problems 🚀

[@akshaychavan5511]

Amazing as always!

[@business_central]

I am a bit confused about the ops calculations ... can anyone reiterate the intuition here?

[@rikerwilson118]

The intuition is difficult, but it might help if you draw it out on a graph showing operations vs. the minimum number of maxBallsInPag, which and you'll see that there is a point at the maximum number of operations that intersects what is possible. The operations needed for the i-th bag is ops = ceil(nums[i] / maxBallsInBag) - 1, and we do the -1 because of the way that rounding and integer division works in programming. IMO calculating the operations needed for the ith bag is very unintuitive.

[@JamesBond-mq7pd]

You need to find a number by iterating from 1 to the maximum value in nums, where for each number, the total sum of ceil(x / your_number) - 1 for all x in nums is less than or equal to max_operations.

[@top10z38]

@@JamesBond-mq7pd am still nt clear tbh

[@AadityaSPatil]

@@top10z38 Here's my understanding of the ops calculation: Let's try to find how many ops it would take to split an integer, say 13, such that the greatest integer in the end is 3. How do we ensure that the greatest integer we would be left with in the end is 3? We can simply divide the number 13 by 3 which gives 4.33. This means that we would have four 3's and some number smaller than 3 as the remainder. The actual numbers would be [3,3,3,3,1]. In other words, ceil(4.33) = 5 is the total numbers we would be left with. How many splitting operations would this take? It's quite clear that after splitting an integer, the total number of integers increases by 1. We started with 13 (a single number) and got 5 numbers in the end i.e. [3,3,3,3,1]. So, to go from 1 integer to 5, it takes (5-1) = 4 operations. Hope this helps.

[@business_central]

Thank you all 🙌

[@steel_hat_pirates]

it is giving error for [7, 17] and maxOperations = 2, this is giving 5 in LeetCode and when I tried the same in my Machine it's giving 7 which is correct but don't know how it was 5 in leetCode : (

[@sbobbe97]

Same for me but in the while I was doing m = l+((r-1)//2) instead of r-l

[@yashsinghverma5990]

This is probably because you are using C++ and in it if you divide a number and it's in point the part after point is omitted so you should use (double) before denominator see leetcode editorial and test out by outputting with and without double you will understand.

[@Anotherdudeeeee]

Yup, did it in python and got the error as well

[@ahmedtremo]

Thanks for making this video

[@black-sci]

can you do video on 2054. two best non overlapping events

[@tf2videos164]

Technically here we stop when l is equal to r hence why returning res also worked

[@VinayakUpadhyay-u3d]

What software you use for pen tablet?

[@yang5843]

paint3d and a mouse

[@yang5843]

The hints pointed to binary search, this problem is similar to Koko bananas.

[@n0ne0ne]

can you solve some advent of code problems?

[@GANESHKUMAR-ww9dv]

You could've explained a different example mate

[@ssuriset]

4:54

[@IK-xk7ex]

3 weeks ago I recognised and solved similar problem using binary search, but today I got stuck with heap, 😢 shame on me

[@chaitanyasharma6270]

Whats with the random ass algebra

[@OMPRAKASHkumar-bt3es]

Sir make video in Hinglish language 🙏🙏🙏

[@diojoestar5178]

why are u smirking in the thumbnail of the balls in a bag problem 😭😭😭😭😭😭😭

[@DJ-pn9te]

leet code problems for interviews is completely stupid. what is your goal? have 100 people try to solve a problem that has already been solved within 15 minutes. memorize a regurgitate an answer? Dumb Dumb Dumb. you wasted 8 minutes trying to explain the problem, which was not fully clear and now your going to judge a person on how they would solve it? mathematically or with code? And what application is this going to be used for? Another complete waste of time.