BS-18. Allocate Books or Book Allocation | Hard Binary Search

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

[@manrar8419]

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 !!!!

[@mohamedsameer137]

Ur LinkedIn profile ?

[@manrar8419]

@@mohamedsameer137 search for Hriday Rathi, I'm from Plaksha University

[@eshitaaaa]

Hey, I'm also in the same path looking for interns and following his sheet. Would you like to connect?

[@AkshayGoel-of8ic]

​@@manrar8419for sde post, did you do other than the playlist, please tell me....

[@infinity2creation551]

@@eshitaaaa whats your linkedin

[@gunduboinadileep9523]

understood!!.... at 22:30 low = 64 as low = mid+1 => low = 63+1 = 64 : )

[@Codro09]

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

[@HarshKumar-ip5nr]

Can wait to get this playlist completed. Thanks for the free content.

[@VineetKumar-fk2rl]

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

[@Veer_Shiv]

Watching the whole playlist is just like watching anime and waiting for upcoming episodes tooo 😝

[@Lekshmi_sree]

Do you have solve DSA complex problem now?

[@saketsoni2587]

@@Lekshmi_sree yes i guess

[@nikhilkumarjamwal5322]

No manga here tho!🌝

[@omkarshendge5438]

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?

[@secretvibz6300]

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

[@lakshayyadav9850]

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 🌟🌟🌟🌟✨✨

[@aswinbarath]

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.

[@cinime]

Understood! Super fantastic explanation as always, thank you so so much for your effort!!

[@user-it6go3fc8p]

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

[@dipingrover1970]

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 ?

[@user-it6go3fc8p]

@@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).

[@LearnWithRaza-m3b]

​@@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

[@dipingrover1970]

@@LearnWithRaza-m3b 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 .

[@VanshKalra_cpp]

@@dipingrover1970 its simple lets take for eg arr=[1,2,3,4,7] and m=4 but acc to our algo 1st student will take 1+2+3 =6 pages then second will take 4 and 3rd will take 7 and we will never reach cnt of students==m==4 therefore condition should be cntstun return -1

[@084abhigna_y8]

No words to express my gratitude towards the man teaching here 😇

[@1tav0]

Yes!! thank you so so much for the dp and graphs series sir much love and gratitude from ca !

[@arujain1690]

It is hard, one of the question i didn;t get even after reading it like 5 times. Nice explaination as always!

[@studynewthings1727]

Hi Striver, I watched solution, linear Search wala part twice and I got the point. Thankyou So much.

[@VishalKumar-bj4nl]

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.

[@harshith4549]

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

[@mrinalchoudhary7525]

Your explanation is insane. Hats off.

[@user-hk4oc4dz2k]

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. 🙏🙏

[@devateja9045]

Man, you are just awesome. More power to you

[@shankargowd9777]

This problem is quite similar to "allocate minimum number of pages" and "painters partition" problems

[@stith_pragya]

UNDERSTOOD...Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@ishangujarathi10]

lovedd the intuition!! understood completely!!! tysmm

[@52_it_rohitmukherjee99]

what an explanation ! clearly understood .

[@footballcreativeeverywhere260]

What a tumbnail man !!! ❤️ , Just wow ....

[@user-ti3bd8mp1w]

understood Thank you striver for such an amazing explanation

[@abhayroadlines528]

Thank you so much for this wonderful explanation♥

[@user-dd8bi1ni2k]

Thank you brother now I finally understand this kind of pattern

[@vedfutane7995]

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

[@pratyushraj2629]

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?

[@tanishtha-dj1wu]

hey i am facing the same problem.If you had made an excel for that,kindly share it @pratyushraj2629

[@manavsingh5919]

Thank you Striver Understood Everything🙂

[@hetpatel7399]

Happy Guru Purnima teacher+bhaiya :)

[@abdussalam-4836]

after watching the whole playlist this question was easy for me

[@Roshan__3006]

Danger bro, amazing my doubt is clear about is question Thank you for your videos.

[@ujjawalraj6096]

This is not an tough question if you are following this playlist this is an cakewalk Solve by own Tysm Understood everything❤

[@varungoyal3071]

Amazing explanation!!

[@adityarajvermaa]

again even this one .....i coded by myself..thanks bhai

[@riteshbisht94]

Stunning 🎉

[@Shunya_Advait]

Understood easily Sir, Thanks a lot .

[@AjithKumaR-jw9wt]

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

[@artofwrick]

A god kind of explanation ❤❤

[@ritwik121]

What an explanation. Thanks striver.

[@AjithKumaR-jw9wt]

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

[@anish-acharya]

This video is more understanding then code help's allocate books. Thanks

[@AjithKumaR-jw9wt]

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

[@harshitpatil6138]

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

[@VivekKumar-kx2zf]

@@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.

[@VivekKumar-kx2zf]

@@harshitpatil6138 in that case 10 should be the answer🤔

[@Freefire-hp4zz]

Waiting for STRING PROBLEM PLAYLIST STRIVER BHAI HOPE YOU WILL DO IT BEFORE MY PLACEMENT STARTS

[@sanchisingh481]

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 😄

[@devils9844]

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

[@takeUforward]

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.

[@ambaradhikari7425]

@@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.

[@kshitijkumre9895]

@@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

[@sanchitdeepsingh9663]

these are the toughest ques on BS , there is also feel of CP in these ques

[@MJBZG]

could solve it myself, thanks!

[@NazeerBashaShaik]

Understood, thank you.

[@YourCodeVerse]

Understood✅🔥🔥

[@mhsunny123]

Exactly same question as LC 1011 : Capacity to Ship Packages within D Days

[@tejaswaniguttula5961]

@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

[@fettuccine794]

Striver is GAWDDDDD man !!! I wish I hadn't wasted my time watching Kunal Kushwaha's videos.

[@atharvameher5880]

I am watching Kunals what do I do? Where did he go wrong?

[@fettuccine794]

​​@@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

[@akworld2739]

@@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

[@fettuccine794]

@@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 !!

[@fettuccine794]

​@@akworld2739, stop watching many tutorials, 1st try to do the problem for 30-40mins by yourself then watch the solution

[@ambaradhikari7425]

Bhaiya thank u for the solution, please complete within next 2months if possible placement season coming up, please bhaiya

[@rushidesai2836]

Had to watch it twice. One of the most intersting questions I have ever seen.

[@user-is6ky7pp2n]

Understood !! 😍😍

[@user-zn4xn9qx2n]

Understood and thanks😊

[@NitinKumar-wm2dg]

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.

[@rohanpathak]

Bhaiya thanku for the course, but kab tak complete hojaaega course??❤

[@user-mc6sb4cm9p]

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??

[@aggarwalsachin4854]

yes

[@ankitraj2283]

yes bro

[@madeinhvn]

yes exactly what i thought

[@nishant8581]

Amazing video

[@tusharnanda744]

understood ! completed 335 / 454 of A2Z all beacuse of striver . Thanks a lot

[@eshitaaaa]

Hey, im on the same path, would you like to connect and share your coding journey?

[@cp65143]

How many days it takes generally

[@PiyushKumar-xe1ng]

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

[@Sim_tim]

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

[@googleit2490]

Understood, was enough difficult though!!

[@mayankshakya9200]

Sir plz next episode plzzz And one question: ki next konsa topic cover karaoge after binary search ??? ❤❤❤❤

[@preetisahani5054]

hats off to your effort!

[@AjithKumaR-jw9wt]

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

[@preetisahani5054]

start from low, check no. of students required for that and keep increasing if student count comes to be greater that 3

[@AjithKumaR-jw9wt]

@@preetisahani5054 I dry run with above example in striver code it give wrong answer, first it will take 8

[@user-or5oz1pk2x]

Thanks a lot Bhiya

[@sangeeta35]

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

[@aadharjain313]

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.

[@her_soulmate]

Understood 🎉

[@suchitpatel8700]

thanks striver 😄

[@kshitijkumre9895]

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😔😶😶

[@niceguy3773]

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....

[@sohampal1596]

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.

[@GauravJain-zo8gt]

jai jinendra sir

[@koushtubhvikramaditya1467]

Can you tell what app you are using for explanation? Thank you

[@Abhay14]

Thanks bhaiya

[@alamkhan6688]

sir plz add gfg link in striver SDE A to Z sheet we are halfway done to it

[@daniarp8958]

One doubt, when to start count in helper function with 1 and when to start with 0 ?

[@kishorebalakrishnan9283]

Is DSA a to z playlist finished or ongoing series because I couldn't find notes and vedios for few problems

[@Rohangamin517]

Very easy😊😊

[@RaviKumar-sn6tu]

understood!!

[@shubhamsharma-nb8yd]

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 ..

[@firebout7675]

understood

[@shivangkhandelwal334]

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 ????

[@piyush29864]

it wont work. Window size can vary

[@NamrathaSairam]

When do we use the opposite polarity concept and when do we use the return mid concept, I am a little confused.

[@shivarajpatil8699]

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.

[@takeUforward]

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 :)

[@profesor6885]

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 ?

[@amitranjeetjha1240]

Understood

[@ritikanand3425]

What if it return a value which cannot be made made by adding the number of pages in array

[@siddharth892]

But what if the subsequences were allowed as in the allocation of books could be discontinuous.

[@user-js1rx8rs9p]

understood striver

[@Spidey__Gamer]

bro can you hlp me plz... i java basics... shd i learn cpp for following ur series??

[@chaitanya812]

in which video he explained that always low will be the answer?

[@MJBZG]

hats off to the people who think of these questions like bro who hurt you🥴

[@shatwikshankar05]

bhaiya, can you please recreate your Greedy algo problems video from SDE sheet......basically editor syntaxing me problem aari...after repetitive try...just 3-4 videos🙁

[@shaiksoofi3741]

underatood

[@arijitdas1965]

❤️❤️❤️

[@pranjaltomar2629]

🔥

[@Raj-yr3vz]

it was asked in my PayPal OA

[@pihus3498]

understood :)

[@sachinvarma9949]

Sir ❤❤❤❤❤❤