Allocate Minimum Number Of Pages
Вставка
- Опубліковано 15 вер 2024
- ALLOCATE MINIMUM NUMBER OF PAGES:
Given number of pages in n different books and m students. The books are arranged in ascending order of number of pages. Every student is assigned to read some consecutive books. The task is to assign books in such a way that the maximum number of pages assigned to a student is minimum.
Example :
Input : pages[] = {12, 34, 67, 90}
m = 2
Output : 113
Explanation:
There are 2 number of students. Books can be distributed
in following fashion :
1) [12] and [34, 67, 90]
Max number of pages is allocated to student
2 with 34 + 67 + 90 = 191 pages
2) [12, 34] and [67, 90]
Max number of pages is allocated to student
2 with 67 + 90 = 157 pages
3) [12, 34, 67] and [90]
Max number of pages is allocated to student
1 with 12 + 34 + 67 = 113 pages
Of the 3 cases, Option 3 has the minimum pages = 113.
PROBLEM STATEMENT LINK:www.geeksforge...
PLAYLIST LINK: • Binary Search | Interv... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
Related Problems For Practice :
Book Allocation Problem (GFG)
Aggressive cow (spoj)
Prata and roti (spoj)
EKO (spoj)
Google kickstart A Q-3 2020
+ Painter Partition Problem
@@TheAdityaVerma + Below Leetcode Problems
1482 Minimum Number of Days to Make m Bouquets
1283 Find the Smallest Divisor Given a Threshold
1231 Divide Chocolate
1011 Capacity To Ship Packages In N Days
875 Koko Eating Bananas
Minimize
774 Max Distance to Gas Station
410 Split Array Largest Sum
@@shubhamchaudhary8688 Thanks a lot and @ashish choksi for mentioning related problems just because of you guys now I have good command at these types of problems
thanks
@@shubhamchaudhary8688 thanks it helped alot..
I like how he has never mentioned at the start/end of any video to like,subscribe,comment like everyone else does. Just pure meaningful content !!!
i just needed help...what about if student is < k ? why is there no condition for that??
@@divyareddy7622 I tried using
return student == k ;
which will return accordingly
@@divyareddy7622 Actually this condition should return "true" because if students < k that means we have distributed some extra books to a particular student, in that case we can take the extra book from that particular student and give it to a new student until the condition becomes students == k.
This condition is already handled in isValid() function when we return true at the end of function.
For example:- consider the following testcase:
n = 7
array = 15 10 19 10 5 18 7
k = 5
distribution for max = 25: [[15, 10], [19], [10, 5], [18, 7]] : no. of students == 4. But, we can easily take one book from a student and give it to a new student which will give us a no. of students == 5. In this case the function will return true.
Thank You.
@@divyareddy7622 you will not be in that case , start is the max element in the array , end is the sum , mid is the half of start +end ,you cant fill all the (sum of all pages ) to the mid , some pages(sum-mid) will go out of the capacity (mid) of first student . hope this helps XD:::
Can't believe we're getting such superb quality videos for free.
i just needed help...what about if student is < k ? why is there no condition for that??
Give this guy a grammy for such an awesome explanation of one of the toughest questions :D
I had a similar question asked int the Uber interview and I was blackout, literally impossible to solve this kind of question if you've not solved it before.
Though I solved it using brute force - Recursion but that wasn't the expectation.
This is a unique kind of pattern and I must say I learned a new pattern today. Though I strongly believe that such questions shouldn't be asked as it doesn't check your problem-solving skills.
Awesome explanation, couldn't find anything better on the internet for this problem.
I have a doubt why is there no condition for students
@@hahahaha4217 we divide the array into k parts so students cant be less than k, think of it this way.... you divide 100 in 3 equal halves, now you cant have 2 halves with both less than 33 and also add up to 100 as well.
@@hahahaha4217 Actually this condition should return "true" because if students < k that means we have distributed some extra books to a particular student, in that case we can take the extra book from that particular student and give it to a new student until the condition becomes students == k.
This condition is already handled in isValid() function when we return true at the end of function.
For example:- consider the following testcase:
n = 7
array = 15 10 19 10 5 18 7
k = 5
distribution for max = 25: [[15, 10], [19], [10, 5], [18, 7]] : no. of students == 4. But, we can easily take one book from a student and give it to a new student which will give us a no. of students == 5. In this case the function will return true.
Thank You.
You give Best explanation available on UA-cam..It's helping me a lot..
Bhaiya, I have started CP and was struggling in implementation of Binary Search. I watched your full playlist and it really helped me a lot in implementing Binary Search. Thanks.
This is the only channel where i understood this problem. Hats off and thanks for all your hardwork and efforts. You are a great teacher 👍
Just started with your dp videos it's amazing and best till date... Also request you to please make graph playlists. Eagerly waiting 😊
can i do dp before recursion ? If not please tell about a good recursion series (apart from take u forward). Thanks
@@pranav288 no
@@pranav288 Pepcoding Sumeet sir ke recursion videos. Top quality. And Doing DP without knowing recursion is waste and almost impossible.
i just needed help...what about if student is < k ? why is there no condition for that??
i just completed this playlist and once again want to thank you brother ! people usually consider binary search topic very easy and leave it, to all those reading this go ahead and watch this playlist from the start you guys wont be disappointed and will definately learn something new .Thank you Aditya bhai !
Lecture 41 mins ka hai lekin feel nahi hua ki bohut lamba hai jab sunn raha tha. Upar se concept barhiya se samaj aa gaya. Thank you aditya bhaiya! ✌
Even though your Binary Search playlist is sorted in quality of conceptual knowledge,
Yet we can't jump to either half of your playlist 😅😅
This is how legends summarize Binary Search playlist 😂😂
haha good one
started on 14/7/23,5a.m. and was able to complete this masterpiece series successfully at 15/7/23,3:50 a.m., Grateful for this series.❤💙
thank you so much for all the work you put into your videos, made tough topics like DP seem so simple.please upload more videos on important topics and questions from placement point of view, and maybe some tips and tricks also. You're like that friend who teaches imp topics 30 mins before the exam and all that only comes in the paper🔥🔥🔥 eagerly waiting for all the upcoming vids, i have notifications on!!
Thanks a lot for all that appreciation ✌️😅
@@TheAdityaVerma Men will be Men hahaha
@@SandeepKumar-qw3tv phirbhi sbse lamba creative comment yehi hain haha
@@SandeepKumar-qw3tv I saw that, he only replayed to women...😅😅😅😅😅😅
This is the best explanation, I have ever seen. TYSM brother🙌❤
Amazing Explanation!
I had spent 11 days thinking and trying to solve but you explanation was extremely clear.
same goes with me
Really cross through the best teacher all over you tube ....the way you teaches is like making most difficult question as cup of tea for us ....thanks a lot ❤️
14:04 --> as per the given condition, no student can be left idle, so the start index should be bigger than 0 & the end index would be lesser than 100. To assign a student with a book, minimum one book is to be given for sure. Maximum pages he/she will read = max(arr) ...
right because if arr[]={10,60};
in this case mid ==35;
and isValid function returrn true ; //which is not acceptable.
Sir please backtracking k upar bhi ek playlist upload kr dijiye as it would be very helpful for students whose placement session is approaching
If youtube had a love react, every video of yours would get that from me !!!!
Flawless!
As someone who likes teaching, I really look up to you :)
Hello Aditya,
You are explaining very well. Please upload the next playlist ASAP and then keep adding the next videos. It would really help.
i just needed help...what about if student is < k ? why is there no condition for that??
"To me to fan hu, tum bhi ban jao.. Thankyou" Best line bhaiya, we are already your fan.
As mentioned in the start "this is going to be the best question so far", indeed it was, and the explanation was just as amazing as the question, thanks Aditya.
i just needed help...what about if student is < k ? why is there no condition for that??
i buy online course but i understand better here...best explanation ever.. thank you
completed this series in two days, really amazing ❤❤
same here... completed today in two days!!!!
Completed this played in 2 days... It took 6-7 hr approx. To complete it. Thank you so much for creating such a great content. 😀
Very nice video bhaiya!!!!!
For reference:
#include
using namespace std;
bool valid(int arr[], int n,int s, int max){
int students=1;
int sum=0;
for (int i = 0; i < n; ++i)
{
sum=arr[i]+sum;
if (sum>max)
{
students++;
sum=arr[i];
}
}
if (students>s)
{
return false;
}
else
return true;
}
int binarySearch(int arr[],int n, int s){
int result=-1;
// if books is less than students
if(n
i just needed help...what if students is < k ? why is there no condition for that??
@@divyareddy7622 watch take u forward video on the same question
@@divyareddy7622 do you get ans?
No@@Amansingh-gi3gx
Bhai bhut mast padhte ho tum bhagwan tumhe kamyabi ki nayi uchaio p le jaye
Sir i am literally crying right now because of two things 1.) I don't have a mentor or a teacher like you (but now we have you) 2.) Your simplicity level made me so so emotional Once again sir thank you so much : )
i just needed help...what about if student is < k ? why is there no condition for that??
@@divyareddy7622 there is one condition you need to allocate atleast 1 book to every student thats why number of student is not less than k
@@divyareddy7622 k is itself number of students given
Finally finished this..Eageraly waiting for other playlist..Your every playlist is very helpful..thanks a lot
It won't give the correct output in the case ,
n=5
arr[] = 51 151 227 163 55
m=3
Correct output : 227
Output from this code : 257
@Aditya Verma Sir please pin this comment so that others can correct it !
In isValid function we need to mention one more condition inside for loop i.e.
if(arr[i]>mx)
return false;
, because as soon as any individual element's value gets greater than our threshold value mxs it is not possible that maximum sum of any subarray is less than or equal to mxs.
You are right , i added this statement in isvalid() part and the solution was accepted
bro that's why we take start = max element in the array.
But why should u add that condition it will anyway return false once student goes above the value of k right...? Can u please explain y it is necessary to add that condition
what is most fascinating about his explanation is that you are able to code by yourself before the video arrives at its mid .
i mean who needs the code? when concept is crystal clear .
awesome video,
I tried this question before,but i didn't understand it.
but youuuu explained it so deeply that now i understood it very well.
Sach me aap to CODING KE BAAP h.
coding krna to koi aap se seekhe
Thanks Shikha !! 😅😅I hope that you wont forget it now and could do it the next time when you get across a question like this.
Sure I will never forget it
@@TheAdityaVerma bhaijaan batado ab ki iss mahine kuch aaega ki nahi. Roz roz ka intezar maare jaa rha hai merko
Finished the playlist and literally I am feeling confident now in BS...Thanks a lot, buddy :).The best thing is ki by solving and watching you how you tackle the problem it created an automatic process ki haan aisa hai to maybe we can apply that..
Hi Aditya... Your tutorials are awesome!! ... Could you please share the list of problems if you have handy which are similar to this "Allocate Minimum Number of Pages" problem concept?
After finishing this playlist, I am just thinking🤔 why you stoped teaching a year ago? Being such a great teacher you should start making videos on other topics also as it will help students in their journey of learning DSA.
i just needed help...what about if student is < k ? why is there no condition for that??
@@divyareddy7622 that means there is less Books are present in the array as number of Students or one book in the list which not possible to distribute in both student i.e. -1.
@@divyareddy7622 I have the same doubt
how are we ensuring that each student is getting at least one book ?
which logic is taking care of that part ?
we are checking student > k , return false , what if student < k at end ??
did you find the answer for that ?
@@ashwinbhargava3011 I have seen this comment somewhere
Not tried yet , check if it works out for you
" I feel like. Since in the isValid function we check for k==M and for k
great explanation , i came here after watching lots of videos on the same topic but nobody explained better than you. Hats of to you bro , ur channel is so underrated but I wish all ur hard work and skills will be much valuable in future.
i just needed help...what about if student is < k ? why is there no condition for that??
@@divyareddy7622 'K' is the number of students. array indexes represent the book numbers and value of arr[i] represent the number of pages in it the array of any particular book.
Bhai, at this moment, I have seen all videos of yours. I can't thank you enough. You are brilliant. 🙏🙏🙏🙏 You are a blessing. 🙏🙏
Please upload videos on RECURSION and BACKTRACKING. Please. 🙏🙏🙏🙏🙏
"Tu khel jaake maje kar" 🤣🤣🤣🤣🤣🤣
Sir, really really thanks for these awesome videos. I was initially struggling with binary search , but your playlist helped me a lot. Please make videos on graph theory and other imp topics.
And phir se Sir, really really thanks🤘
bestest and simplest explanation of this tough problem on the internet, thank you so much, sir!
love the way you treat the code ! never get such amazing content in free. lots of Love from NITW
Hi Aditya, Kindly include problem "Median of two sorted array" in your binary search playlist. This question most frequently asked by companies.
Bro You are Awesome! Raat ke 1 baj rahe hai but apke videos dekhke kabhi bore nahi hua hu. Aur padhne ka mann karta hai. Great series man! Keep up the good work.
awesome great mind blowing faad pelu zabardast aur kya bolu bhai abhi itna hi aa rha dimag me .. aur aayega to phir likh dunga
Thank you from bottom of my heart. These videos are very helpful.
Eagerly waiting for your upcoming videos.
"students ka stress reduce karna hai " bus yahi ek line thi jiski vajah se me pura algorithm proper samaj paya
puri series dekhi kuch samajh nai aaya y question lekin ek bar m hi samajh aagya ,thanks a lot sir
bro i was totally confused before looking to your video
you just nailed it thumbs up man.
subscriber++;
Learning the Best from THE Best
One thing to note here is that in isValid function we're simply putting the array values without even checking that even an individual book may contain pages greater than maxPages passed into the function so we have to take that case into consideration while writing code otherwise it will simply call the statements inside if block and count will get increased and in the next iteration value stored in sum(or books) will be replaced by any other value .
bool isValid(int maxPages,int *A,int N,int M)
{
int count=1,books=0;
for(int i=0;imaxPages)
{
books=A[i];
count++;
if(count>M)
return false;
}
}
return true;
// (count
GFG test cases are too weak i did it without taking the above point in consideration and it still passed but while doing painters partition problem on interview bit i had too add this condn to just pass the sample case !
Hello r u here I have one doubt..
Please make a playlist on dfs and bfs related questions. Thanks alot for all the help!
one condn is left in isValid func ------> if(a[i]>mid) return false ; else kuch case me ans galat aa rha h. Thankyou for this awesome explanation.
Thanks a lot bhaiya for such a lovely & simple explanation
my friend suggested your chanell and now i will show i am happy with your vedio now you won new subcriber as me😊😊.. but bhya i noticed it's about a year you dont even post single vedio....please dont leave youtube😥😥...please keep sharing this tricks for 2-3 year student like us....
Loved the explanation probably one of the best :)
C++ Code for those who got stuck, yea if u did got stuck, go get some hands on other stuffs coding is really not for u , aditya wrote every code on a paper but still u got stuck : (
class Solution
{
public:
bool isValid(int arr[],int mid,int n, int m){
int student=1;
int sum=0;
for(int i=0;imid){
student++;
sum=arr[i];
}
if(student>m) return 0;
}
return 1;
}
//Function to find minimum number of pages.
int findPages(int A[], int N, int M)
{
//code here
if(N
for further optimising the code.. we have to initialize the start pointer to min of the array right? But in the video he has initialized the start pointer to max of the array ,i.e 40
The optimization that you told regarding setting low to max fo array is required..if someone starts if from 0 ro min of array, isValid function will fail for lower ranges, hence giving wrong output..
anyway lower range, wont be having the answer.. hence, set it to max of array to make the isValid function work correctly.
To understand it better take a small case of 5 in the same input, isValid function will pass the value and will give wrong output.
Hence, its mandatory to set it to max of array
Thanks, Aditya. One of the best videos to learn BS.
Ok so for any one who started with low=0 instead of low = max element in array. Just check one more condition iside valid functions for loop i.e if(A[i] > mid) return false; because there can be a scenario when m elements are there but last one is greater then our limit. Or the best thing is to take low = max element in array
thanks. this helped!
Thank-you so much...this application of binary search is very very useful and being used in many areas if we look very closely...I'm shocked even it is used in "Ugly numbers III" and is far better than DP :>
Thank you very much.
great explanation,I think we can optimize isvalid function to O(log(n)) from O(n).like we can store array sum as sum upto this element and find range for first student.then find range in right section in sum array for S2.little complicated!!!!
Chal chal hawa aane de...bada aaya coder
I liked the video in the first half, after watching code, I wanted to like it again.😂😂
Thinking directly about this approach may not be possible in an Interview. We would start with simple recursive solution and then optimizing the solution we may end up with the Binary Search on Answer solution. So a recursive solution for the problem is,
def solve(A, B):
def helper(curr_val, n, students):
if n == 0:
if students == 0:
return curr_val
else:
return float('inf')
if students == 0:
return helper(curr_val+A[n-1], n-1, students)
else:
same_student = helper(curr_val + A[n - 1], n - 1, students)
different_student = helper(A[n - 1], n - 1, students-1)
return max(curr_val, min(same_student, different_student))
# just some base cases
if not A or B > len(A):
return -1
elif B == len(A):
return max(A)
elif B
Watched every video of this series and I could say that after your explanation and observation phase of the problem I was able to write whole damm code by myself I am really thankful to you coding was never that much easy until youtube recommendation introduce you to me. Thanks Aditya for make coding easy for us.
Bhaiya please backtracking aur recursion ka playlist de dijiye😢🙏
Brother, it will be out before placements gonna start.
Bhaiya, please share these topics as soon as possible..due to Covid, my internship is going on right now and my ppo interview will be in June mid..
I would be grateful if you could share it earlier than planned.. so that students like me can benefit too..
Thanks a lot Bhaiya
PS - Bhaiya you are a blessing for people like me! Thank you for this initiative!
@@TheAdityaVerma bhai jaan iss mahine kuch aaega hai kya?
@@TheAdityaVerma liar
@@TheAdityaVerma start ho gaya he please upload rest of the DP and graphs specially
Thank you Sir, Very helpful tutorial, Love from Bangladesh.
Bhai you are amazing
Jo concept aapki videos se built hua aisa kahi nhi mila
Thanks a lot but I request you please continue your series of recursion and graph 👍👍♥️♥️
made so easy the concept of binary search on answer he is a gem guy
Bro please keep making videos they are really very helpful
Bhai bohot sahi explaination
Perfect explanation. Far Better than others!!
bhai best !! watched this vid once and solved all the problems in pinned comment in one go .
Hey, Thank you so much all your knowledge sharing. I am able to perform very nice in all my interviews. Keep up the good work. More power to you.
Keep rocking!!!
bro,can u please guide me/?
At 15:56 ,if the one student gets 40 number of pages ,then another students will get 60 ,then why the maximum number of pages will be 100 ,i didnt get?
The way u explain the problems are really amazing plz make videos on graph and tree also,we are waiting for your videos🥺
Very Nicely explained. Thank You for this amazing video
Maaza aaya
aur ye maaza mai mere saath waalo aur juniors ke saath bhi batunga....
Best Playlist For Binary Search
Wow sir salute to you aggressive cows waala question 1st try m bn gaya.
sem 1 m diya tha humare teacher ne tb ghanta samajh ni aaya tha but aaj ye question dekh kr us question ki yaad aa gaya aur try krte hi ho gaya ❤❤❤
bhaiya completed this series also thanks for ur precious content huge love and support apko,,,..
One small point . one edge is missing . in the array if any element is greater than mid then isValid should return false but currently its returning true
def isValid(self,A, n, k, mid):
students = 1
sum_ = 0
for i in range(n):
# one book can have max pages more than mid
if A[i] > mid:
return False
sum_ += A[i]
if sum_ > mid:
students+=1
sum_ = A[i]
return False if students > k else True
Hey sir, Its was just an amazing explanation of the problem and its solution . THANKS U MADE MY LIFE EASIER
I appreciate your hardwork and smart work
The way you are teaching is excellent. I started learning dp from you but from now I am viewing yor all playlist ❤️
Keep uploading other topics content like graph and tree it will help me a lot
Thanks for uploading this kind of contents
And thanks to you I am finally able to prepare my binary search properly
Binary Search Completed...Thank You Aditya Bhaiya💌
Can you share the list of projects that you have implemented? what is the weightage of projects for selection process?
Amazing playlists!
Thnx a lot bhia..... please keep making more such videos....
Hi Aditya, the explanations are excellent and reflects your great insight and connected understanding. I am sure its helping others like me. Look forward to your Greedy and Backtracking playlist. Cheers.
you explained this in the best way...
keep it up!!!👍👍
thanks aditya bhaiya to make understandable that problem ,
i was not understanding on other channels
love you sir kya samjhaya hai sir apne ye sum❣❣
Thanks a lot.
Best explanation. Keep up the good work.
You are amazing after watching your videos now i am able to do even those questions which i thought yeah nah ho payega. Thank You so much.
aditya please clarify!!!!!!!!
if (student
I also have the same thought. There should be a separate condition.
The condition discussed in the video is right
For ex: ar = [1,2,3,4,5,6,7,8,9,10], k = 5
mid = 32 -> k = 2
Suppose the return condition is return student == k
So in this, it will return false and hence lo = mid + 1 = 33 (with increasing lo, students will become less)
But in contradiction we need to minimise the total stress(pages to read) without violating the first constraint
So the condition return student
Sir u are great. The way you teach is amazing. Thank you so much sir for your efforts.
Thank you brother, you explained it so nicely. Looking forward for your next videos
if let's say, in the isValid() function students count is less than k , should we not return False then? as we need count to be k.
I have same doubt , please reply if you get any answer from anywhere ?
did you find the answer for that ?
Same doubt
Another explanation (for logic building): We need to reduce the maximum books allocated so that its minimum among all the permutation.
The logic for this is: Allocate ~maximum number of books possible to all the students. - Think about it, you are trying to allocate as much books as possible to each students - (which is equivalent to reducing the maximum value).