Allocate Minimum Number Of Pages
HTML-код
- Опубликовано: 16 сен 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??
You give Best explanation available on RUclips..It's helping me a lot..
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.
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.
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 !
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??
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 👍
This is the best explanation, I have ever seen. TYSM brother🙌❤
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??
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
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...😅😅😅😅😅😅
Amazing Explanation!
I had spent 11 days thinking and trying to solve but you explanation was extremely clear.
same goes with me
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??
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! ✌
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.
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
i buy online course but i understand better here...best explanation ever.. thank you
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
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
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 :)
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
completed this series in two days, really amazing ❤❤
same here... completed today in two days!!!!
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.❤💙
Sir please backtracking k upar bhi ek playlist upload kr dijiye as it would be very helpful for students whose placement session is approaching
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. 😀
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
love the way you treat the code ! never get such amazing content in free. lots of Love from NITW
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..
Thank you very much.
Bhai bhut mast padhte ho tum bhagwan tumhe kamyabi ki nayi uchaio p le jaye
bestest and simplest explanation of this tough problem on the internet, thank you so much, sir!
"To me to fan hu, tum bhi ban jao.. Thankyou" Best line bhaiya, we are already your fan.
Thank you from bottom of my heart. These videos are very helpful.
Eagerly waiting for your upcoming videos.
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?
Loved the explanation probably one of the best :)
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.
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
Learning the Best from THE Best
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
"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🤘
puri series dekhi kuch samajh nai aaya y question lekin ek bar m hi samajh aagya ,thanks a lot sir
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. 🙏🙏🙏🙏🙏
Bhai bohot sahi explaination
Hi Aditya, Kindly include problem "Median of two sorted array" in your binary search playlist. This question most frequently asked by companies.
awesome great mind blowing faad pelu zabardast aur kya bolu bhai abhi itna hi aa rha dimag me .. aur aayega to phir likh dunga
bro i was totally confused before looking to your video
you just nailed it thumbs up man.
subscriber++;
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.
Perfect explanation. Far Better than others!!
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.
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!
Thanks a lot bhaiya for such a lovely & simple explanation
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 .
I liked the video in the first half, after watching code, I wanted to like it again.😂😂
made so easy the concept of binary search on answer he is a gem guy
Thanks, Aditya. One of the best videos to learn BS.
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 :>
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..
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
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
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.
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
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).
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
Thanks for the wonderful explanations and videos !!
Please make a playlist on dfs and bfs related questions. Thanks alot for all the help!
bhai best !! watched this vid once and solved all the problems in pinned comment in one go .
Maaza aaya
aur ye maaza mai mere saath waalo aur juniors ke saath bhi batunga....
And thanks to you I am finally able to prepare my binary search properly
You're an exceptional teacher.
love you sir kya samjhaya hai sir apne ye sum❣❣
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
Bro please keep making videos they are really very helpful
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....
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
Thanks a lot.
Best explanation. Keep up the good work.
Best Playlist For Binary Search
Thank you Sir, Very helpful tutorial, Love from Bangladesh.
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
"students ka stress reduce karna hai " bus yahi ek line thi jiski vajah se me pura algorithm proper samaj paya
Thank you brother, you explained it so nicely. Looking forward for your next videos
Very Nicely explained. Thank You for this amazing video
thanks aditya bhaiya to make understandable that problem ,
i was not understanding on other channels
you explained this in the best way...
keep it up!!!👍👍
very goooood,,,vaaaaaaaaaaaaaaahhh bro.
Thank you for this amazing series. ♥♥♥
static boolean isValid(int arr[],int n,int m,int pages)
{
int s=1;
int sum=0;
for(int i=0;ipages) return false; // this case missing in vdio without this case your code will not submited
sum=sum+arr[i];
if(sum>pages)
{
s++;
sum=arr[i];
if(s>m) return false;
}
}
return true;
}
thnks for explanation ,it is great
GFG Accepted Code::
bool isvalid(long arr[], long n, long k, long mid)
{
long long stud = 1;
long long sum = 0;
for (long i = 0; i < n; i++)
{
sum += arr[i];
if (sum > mid)
{
stud++;
sum = arr[i];
}
if (stud > k)
return false;
}
return true;
}
long long alloc(long arr[], long n, long k)
{
long long s = *max_element(arr, arr + n);
long long e = 0;
for (long i = 0; i < n; i++)
e += arr[i];
long res = -1;
if (n < k)
return -1;
while (s
Thnx a lot bhia..... please keep making more such videos....
where is the fault in this for the test case when arr= {1 17 14 9 15 9 14 }, no of student=7, size of arr=7;
Please correct the fault;
bool isValid(vector &arr, int size, int nofStudent, int mid){
int studentCount=1;
int sum=0;
for(int i=0; imid){
sum=arr[i];
studentCount++;
}
if(studentCount>nofStudent){
return false;
}
}
return true;
}
int findPages(vector& arr, int n, int m) {
if(m>n) return -1;
int sum=0;
for (int i : arr) {
sum += i;
}
int start=0, end=sum, mid= start+(end-start)/2;
int ans=-1;
while(start
bro please help me for clearing this testcase
@@__priyanshu__sharma____ sum-=arr[i];
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 ❤❤❤
Binary Search Completed...Thank You Aditya Bhaiya💌
Here is my code for the same:
class Solution
{
public:
//Function to find minimum number of pages.
bool is_valid(int* arr, int n, int m, int mid){
int count = 1;
int sum = 0;
for (int i = 0; i mid){
count++;
sum = arr[i];
}
if (count > m) return false;
}
return true;
}
int findPages(int arr[], int n, int m)
{
//code here
int start = *max_element(arr, arr + n);
int end = accumulate(arr, arr+n, 0);
int res = -1;
while (end >= start){
int mid = start + (end - start)/2;
if (is_valid(arr, n, m, mid) == true){
res = mid;
end = mid - 1;
}
else start = mid + 1;
}
return res;
}
};
Amazing tutorial, Thanks brother!!!
Can you share the list of projects that you have implemented? what is the weightage of projects for selection process?
Amazing playlists!
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?