Book Allocation - Google Interview Question | Binary Search [Hinglish]

Min Book Pages Allocation Problem based on Binary Search.

[itzcs]

Excellent Explanation . I think time complexity will not be O(nlogn) it will be O(nlog(min+max)). ex:- if n=4 ===> 14, 16, 17, are the array elements then time complexity will not be 4log4 it will be so even for less number of array elements with a very high value the time complexity may sometimes exceed the dp based solution which is O(n^2).

[sujoyseal]

Great thinking . I understand how to think binary search problems. It's all about converging the search space. Thanks @codingblocks

[NatureNomad]

Need an additional conditional statement in isValidConfig() under for() loop .
if books[i]>ans, then return False .

Without this the code is failing the following case
Books = [ 97, 26, 12, 67, 10, 33, 79, 49, 79, 21, 67, 72, 93, 36, 85, 45, 28, 91, 94, 57, 1, 53, 8, 44, 68, 90, 24 ] #total 27 books
Students=26

Expected Output : 97
Code shows : 43

[siddheshbandgar]

Very good explanation. Each step explained in great detail. Thank you so much!!

[ShubhamSharma-ncrf]

Wonderfully explained each and every single steps, great work :D

[sirjan]

cant we precompute a prefix sum array and use lower_bound in vectors to see lesser value than mid

[geetanjaligoyal]

Awesome work sir ..Really a great help :)

[vinothkannans]

Excellent explanation with optimized code 👍

[PrateekGole]

Thanks a lot, I read a couple of blogs but this video is much more easy to understand.

[Zephyr-mspg]

Isn't search space at 5:00 should be 40 to 100 ?

[darshantawte]

This question has changed now the array is now unsorted . The only difference change we need to do is the search space will be from (max_val, sum_of all values) .

[ajai_dubey]

Prateek Bhaiya. ✌️✌️🤘. Teachers like you are a hope to students having a dream to excel in their journey. 🙏🙏. Keep sharing the good work Bhaaiya. ❤

[AlokGuptakumar]

Bhai which software did u use to explain the working ...pencil wala?

[AnilBhaskarBhaskey]

Great explanation, thank you for sharing the video. I have one question..How did you come up with a fact that when n can be upto n^5, we can not (should not) exceed order of nlogn?

[vithleshkumargupta]

Very good explanation. Thanks you very much.

[rishabhsharma]

Its been 5 years and still I come back to this video only to understand the solution.

[RahulKumar-quvz]

how is the time complexity Nlog(N) ? the search range is the sum of all N elements which will be much larger than N.

[anjana]

Superb explanation sir!
Sir can you please clear one query that will this method work even if array is not sorted?Thank you

[architagrawal]

thats a very nice explanation...great work

[atulsoni]

Help me Out to Understand The start i.e  s= max(s, book[i]);
I am doing this Program in C# so max is not available in C# ..