BS-18. Allocate Books or Book Allocation | Hard Binary Search
HTML-код
- Опубликовано: 9 июл 2024
- Problem Link: bit.ly/3MZQOct
Notes/C++/Java/Python codes:
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
0:00 Introduction of Course
Hi Raj, Hriday here...I have been following your SDE sheet for a while, and I'm ecstatic to share that I've been offered an SDE intern position at Arcesium in my second year of Engineering, All thanks to youuuu !!!!
Ur LinkedIn profile ?
@@mohamedsameer137 search for Hriday Rathi, I'm from Plaksha University
Hey, I'm also in the same path looking for interns and following his sheet. Would you like to connect?
@@manrar8419for sde post, did you do other than the playlist, please tell me....
@@eshitaaaa whats your linkedin
understood!!.... at 22:30 low = 64 as low = mid+1 => low = 63+1 = 64 : )
Watching the whole playlist is just like watching anime and waiting for upcoming episodes tooo 😝
Do you have solve DSA complex problem now?
@@Lekshmi_sree yes i guess
No manga here tho!🌝
do you go on just watching these videos without looking at the question first by yourself or do u first look at the question yourself and then watch this video?
Can wait to get this playlist completed. Thanks for the free content.
17:30 There is a mistake in condition as (cntStud == m) will be true in this testcase but let pages[] = {25, 46, 28, 43, 50}. In this upto 70 pages, 5 students will be returned from second function but the moment 71 is checked no of student required will reduce to 3 as (25+46), (28+43), (50). And condition cntStud == m will reject it. Note that 71 is the maximum pages a student is allowed to take, so i can distribute (25+46), (28), (43), (50) to 4 students.
Thus condition should be (cntStud
but bro book with 28 pages and 43 pages will be allocated to 2nd person only as maxlimit of pages is 71 how you distributed in 4 persons can you explain ?
@@dipingrover1970 71 is the "maximum limit" a student can hold. As number of students increase it becomes even more easy to distribute so that each of them is having lesser pages than the max limit.
If I have 4 students, i can distribute in this way : (25+46) (28) (43) (50).
@@dipingrover1970 can your give output for arr- 21,32,45,25,78
M=4
The answer will be min pages so 53 but 78 coming how reply
@@Edward.R19 but bro if we take pages less than 78 then it is not possible for a student to take a book alone of 78 pages .
Understood! Super fantastic explanation as always, thank you so so much for your effort!!
I firstly watched the whole explanation till linear search then I was able to write the whole code by myself in binary search. Thank you striver
Yes!! thank you so so much for the dp and graphs series sir much love and gratitude from ca !
Once you explained the logic I wrote the code all by myself for both brute and optimal it's because of your lecture my cognitive skill is increasing thanks a lot❤❤❤
I
The way you got us to think why Binary Search -> was great !!! ...and this is actually what is to be taught in problem solving sessions. thank You very much Striver
Respect++ for Raj bhaiya!!
If i was not learning dsa in such a constructive way idk where would i have been!!
I solved this question by my own all thanks to you for creating this playlist and i am following your AtoZ sheet its amazing!!!
Thanks 🌟🌟🌟🌟✨✨
I have a slight correction in the brute force solution. The countStudent returned from the helper function can be less than or equal to number of students(m) given. (cntstu
You saved my day, Striver bro. I was struggling without the Dry Run of the problem. This video solution is very helpful to understand everything like the approaches using Linear search, Binary Search, the Time Complexity, Dry Run, Intuition and Psuedo code. Thank you so much, bro.
Hi Striver, I watched solution, linear Search wala part twice and I got the point. Thankyou So much.
Man, you are just awesome. More power to you
This problem is quite similar to "allocate minimum number of pages" and "painters partition" problems
Your explanation is insane. Hats off.
lovedd the intuition!!
understood completely!!!
tysmm
It is hard, one of the question i didn;t get even after reading it like 5 times. Nice explaination as always!
what an explanation ! clearly understood .
No words to express my gratitude towards the man teaching here 😇
Sir Your explanation is the best, And thanks to you today I was able to solve this problem by my own without seeing your solution code. 🙏🙏
Had to watch it twice. One of the most intersting questions I have ever seen.
UNDERSTOOD...Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
understood
Thank you striver for such an amazing explanation
Thank you very much sir. I've Been stuck on this problem from the last 3-4 days,watched a lot of videos but your explanation is just on some different level.
Thank you so much for this wonderful explanation♥
Please don't change problem links of A-Z dsa sheet frequently recently all gfg link got replaced with code studio links. It breaks the flow for those who are already preparing from the sheet. Instead of replacing existing links with new link you can add new section for code studio links @takeUforward
yes , you are right , i believe he is being sponsored by codestudio which is understandable but atleast we should get another set of problem on gfg alongside the others . I personally find that the gfg problems are a little more challenging and greater number of solutions are available , hence i choose gfg, what do u say?
hey i am facing the same problem.If you had made an excel for that,kindly share it @pratyushraj2629
Thank you Striver Understood Everything🙂
What a tumbnail man !!! ❤️ , Just wow ....
Thank you brother now I finally understand this kind of pattern
Amazing explanation!!
What an explanation. Thanks striver.
Hi, I have one doubt pls clarify, In linary search approach questions like this arr-8,9,10,50 student-3 in this how linear search works
Happy Guru Purnima teacher+bhaiya :)
Understood easily Sir, Thanks a lot .
Hi, I have one doubt pls clarify, In linary search approach questions like this arr-8,9,10,50 student-3 in this how linear search works
Stunning 🎉
A god kind of explanation ❤❤
This is not an tough question if you are following this playlist this is an cakewalk
Solve by own
Tysm Understood everything❤
Danger bro, amazing my doubt is clear about is question Thank you for your videos.
This video is more understanding then code help's allocate books. Thanks
Hi, I have one doubt pls clarify, In linary search approach questions like this arr-8,9,10,50 student-3 in this how linear search works
Try to minimize your range .Your Range is from 8 to 50 Now you can easily apply linear search on it , and at last your ans will be 16
@@AjithKumaR-jw9wt
@@harshitpatil6138 bro , i was also thinking the same . we should apply the binary search from lowest element to sum of array. but striver didn't recommend it.
@@harshitpatil6138 in that case 10 should be the answer🤔
again even this one .....i coded by myself..thanks bhai
Exactly same question as LC 1011 : Capacity to Ship Packages within D Days
@mhsunny123
Problem 1: Delivering packages (like in the shipping problem):
You have a bunch of boxes (packages) to deliver.
You have a truck with a certain weight limit (capacity).
You can fit any number of boxes in the truck as long as the total weight doesn't go over the limit.
Your goal is to find the smallest truck (capacity) that can deliver all the boxes in D days or less.
Problem 2: Distributing books to students:
You have a bunch of books to distribute to M students.
Each student must get at least one book.
You can't give half a book to a student, they need a whole one (contiguous block).
Your goal is to find a way to distribute the books so that every student gets at least one book.
Why the code checks differently:
In the delivery problem: You're looking for the smallest truck that works. So, if you find a capacity that lets you deliver everything in D days or less, you know you can probably do even better with a smaller truck (hence checking numberOfDays
Understood and thanks😊
Waiting for STRING PROBLEM PLAYLIST STRIVER BHAI HOPE YOU WILL DO IT BEFORE MY PLACEMENT STARTS
Understood, thank you.
found it easier than aggressive cows , when you are able to conceptualise a question in your mind then it becomes easier to write it in a code
Understood✅🔥🔥
Understood !! 😍😍
Thanks a lot Bhiya
could solve it myself, thanks!
Hi raj , A small doubt.
In the brute force approach , why did in the end when none of the possible values worked , we returned max_element of list and not -1. If max_element of list was a potential answer then it should have been taken care in the loop only.
Thanks bhaiya
understood ! completed 335 / 454 of A2Z all beacuse of striver . Thanks a lot
Hey, im on the same path, would you like to connect and share your coding journey?
How many days it takes generally
you know i used the logic of aggresive cows that you had taught in that video and solved this question using a boolean check function , and the runtime beat 100% i know its not that big of a deal haha kabi kabi tukka lag jata hai but it feels good 😄
Hi Raj, in this video at 22.28 we are choosing the right subarray , so we should take the mid as 64 (i.e mid=mid+1) and not 62 .Right??
yes
yes bro
yes exactly what i thought
Hey.... if possible could you please create a video regarding like ... number of other rounds and type of questions asked in those rounds, in product based interviews based on your experience...if possible, it would be helpful.
Thankyou
jai jinendra sir
Understood 🎉
Striver is GAWDDDDD man !!! I wish I hadn't wasted my time watching Kunal Kushwaha's videos.
I am watching Kunals what do I do? Where did he go wrong?
@@atharvameher5880 his videos are good for theoritical understanding but not upto the mark for problem solving , you will not be able to evolve to leetcode medium and end up loads of just easy questions also his playlist is incomplete since 2 years . Watch Pepcoding and Strivers videos they are the best , I am able to solve Leetcode Mediums after watching them
@@fettuccine794 hi please can u tell me how u r practicing problems
have u taken any dsa course i am unable to solve the new problems
kuch easy to ban jate lekin mideum nhi ban pate hai bahi koi tips ho bata ho apne experience se
i am in third year
@@akworld2739 watch the Binary Search playlist by Striver and try to solve them on your own....you can pretty much ace that.....after than if you are doing Java watch Pepcoding videos....watch topics like Hashmaps , Heaps , Priority Queues , Stack , Queues , you will find many Leetcode Medium problems Doable....after that try to Master Recursion which is the most important topic....Pepcoding (Level 1 and Level2) are two of the best Recursion playlist in the internet.....along with Recursion side by side start learning the little Basics of Dynamic programming(just basics) like Memoization.....if you have done enough practice of Recursion , complete LinkedList and Trees....these two are easy topics and are just applications of Recursion....you will be able to solve many Medium problems of these topics.....After all these comes the most important part - Graphs and Dynamic Programming.....for these topic Striver is the best in the internet....better than any other free or paid courses , nobody can beat him....I believe that one should give minimum 3-4 months to Master these topics ....I am also doing DP right now
Hope this answer helps you !!
@@akworld2739, stop watching many tutorials, 1st try to do the problem for 30-40mins by yourself then watch the solution
hats off to your effort!
Hi, I have one doubt pls clarify, In linary search approach questions like this arr-8,9,10,50 student-3 in this how linear search works
start from low, check no. of students required for that and keep increasing if student count comes to be greater that 3
@@preetisahani5054 I dry run with above example in striver code it give wrong answer, first it will take 8
these are the toughest ques on BS , there is also feel of CP in these ques
Bhaiya thank u for the solution, please complete within next 2months if possible placement season coming up, please bhaiya
Understood, was enough difficult though!!
Bhaiya I understand that you want to keep the course at a comfortable pace for better understanding, but i feel the frequencies of the videos should be increased as i think the course is moving too slow.
Maybe its just me, but i thought that i would let you know. Thank you bhaiya for this amazing free course
No it is not that, it's just that lately I have a lot of office work, which does not leaves me with much time, I am just too exhausted, and apart from some topics, almost all are done, so I am going at my pace.
@@takeUforward bro linked list, string, stack, queue, heaps, bit manipulation these are the topics left, if not all the problems but atleast solve few important problems of all the topics.
@@takeUforward Please don't change problem links of A-Z dsa sheet frequently recently all gfg link got replaced with code studio links. It breaks the flow for those who are already preparing from the sheet. Instead of replacing existing links with new link you can add new section for code studio links
Bhaiya thanku for the course, but kab tak complete hojaaega course??❤
Sir plz next episode plzzz
And one question: ki next konsa topic cover karaoge after binary search ??? ❤❤❤❤
understood!!
thank you for the wonderful explanation , i have a little doubt how we are assuring that low is equal to the sum of pages , becoz we are just changing it to mid+1 many times and mid is the average of high and low and there is no surety that mid+1 is equal to the sum elements of array
Please, Do try to complete at least till Sliding Window (or) Heaps (Step:11) of A2Z DSA Course. Only 1 month is remaining for placements😔😶😶
One doubt, when to start count in helper function with 1 and when to start with 0 ?
When do we use the opposite polarity concept and when do we use the return mid concept, I am a little confused.
sir plz add gfg link in striver SDE A to Z sheet we are halfway done to it
I was wondering if we can use sliding window for this problem and simply iterate the window of size (no. of books-no. of students +1) tracking the minimum sum of the elements in the window...Can we use this approach ????
it wont work. Window size can vary
Very easy😊😊
Understood
Can you tell what app you are using for explanation? Thank you
If anybody knows please tell which is the video that explains opposite polarity concept, thank you
koko eating bananas
Thanks ❤️
hey striver please add the gfg links. I have solved many problems on gfg and suddenly it is removed from the A-Z SDE sheet. please give us a choice at least. now my progress is ruined.
understood striver
This is similar to shipping belt question from BS playlist, i solved it and then came here. Your approach helps in solving other question also. Thank you bhaiya.
What if it return a value which cannot be made made by adding the number of pages in array
Bro i am feeling a lot difficult in solving strings and heaps related problems could you please cover those as soon as possible...
I know its difficult for you to manage but atleast can you tell me what i have to do to master these....
Sir ❤❤❤❤❤❤
understood
Hi, i have a question about part of the video with linear search. In that part if and only if helper function returns exactly same number as the number of students it will be satisfied, but if we check it for this test case:
n = 4; m = 3;
books = {24, 49, 24, 49}; The solution should be 73, but when the code gets to that point it will return 2, and so on... So 3 will never be returned; Based on this the array of returned values would look like 4, 4, ... 4, 2, 2, ...
Did I miss something?
And how would this affect on binary search and proofing.
So if its under, it means its possible. As you technically can go from 2 to 3, as you have no such barieer, but you cannot come back from 4 to 3. As you have a barrier :)
@@takeUforward Thanks brother. :D
@@takeUforward Ha ha ha, I was struggling with this same issue since 4pm, and here I got my answer. Basically, even if we allocate books to less number of students for a particular value of 'mid' , that might be a possible answer as we can always reduce the number of *books* received by one student and allocate that to someone else (as 'mid' indicates the *maximum* number of *pages* to allocated per head, allowing us to allocate any number of pages less than 'mid') .
Therefore, we are doing end=mid to preserve this value of mid , when the number of allocation is less than (or equal) the required value.
@@sayantanmanna1360 Is that why the correct way of using "ans" variable is
This
if(painters>k){
low=mid+1;
} else {
ans=mid;
high=mid-1;
}
And NOT (basically I thought we are trying to find first occurrence of k in a decreasing array :) )
if(painters==k){
ans=mid;
high=mid-1; // we can have better answer on left
} else if(painters>k){
// we should increase the time to decrease the number of painters. Therefore go right
low=mid+1;
} else {
high=mid-1;
}
underatood
Is DSA a to z playlist finished or ongoing series because I couldn't find notes and vedios for few problems
understood :)
in which video he explained that always low will be the answer?
Hi I have this small doubt ,
12,34,67,90
if we put this array in compiler , and compute for the helper function as given in solution, we would get answer to be 2 , shouldnt be 3 since the
12,34 | 67 | 90 , would be the configuration ?
But what if the subsequences were allowed as in the allocation of books could be discontinuous.
Striver bhai i didn't understand how the opposite polarity will work in this question? both sides were not possilbe in beginning even the high side then how can we decide in these situtations? ik you said high was kind of possible but i don't think that was clear enough for me. if you could elaborate on that part it would be helpful. Thank you for this series btw! You're doing god's work.
Hi, i have a question about part of the video with linear search. In that part if and only if helper function returns exactly same number as the number of students it will be satisfied, but if we check it for this test case:
n = 4; m = 3;
books = {24, 49, 24, 49}; The solution should be 73, but when the code gets to that point it will return 2, and so on... So 3 will never be returned; Based on this the array of returned values would look like 4, 4, ... 4, 2, 2, ...
Did I miss something?
Someone asked the same question, I gave the below answer
So if its under, it means its possible. As you technically can go from 2 to 3 students by limiting some distribution, as you have no such barieer, but you cannot come back from 4 to 3. As you have a barrier :)
Can add another edge case - if( m == n ) return low;
Adding this makes my code 100 percent efficient from 96.03
:P Just small wins ..
it was asked in my PayPal OA
hats off to the people who think of these questions like bro who hurt you🥴
can we do it with partition dp
❤️❤️❤️
24:50 Opposite Polarity
🔥
Striver please tell how to approach bit magic problems