BS-12. Koko Eating Bananas
Вставка
- Опубліковано 27 вер 2024
- Problem Link: bit.ly/3CmCKVI
Notes/C++/Java/Python codes: takeuforward.o...
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/take...
0:00 Introduction of Course
I see Koko is on a high carb diet😀😅
😂
🤣🤣
Gay
lmao but tbh koko is a monkey i think thats why he is eating bananas!
@@dumpster-jackson wtf
Great tip! Whenever there is a possible range of answers then we can apply binary search.. Thanks a lot Striver!
give this man the best teacher award in the world
In DSA sure is this best For development check chai aur code once
for those who are solving in leetcode the TotalH should be long long and also the CalculatetotalHours should also be long long type otherwise it will throw an error .....
hope it is helpful
it was throwing run time error earlier. i thought i must be missing some edge case . after this change it got submitted. thanks to you buddy
Why to calculate total hours just check if it any instance the req time crosses h... Return false
When I was submitting my code, I encountered the same problem, Thanks buddy.
Bro on LeetCode not working after 121 test cases.
@@tusharkhatri2921 you can make the condition in the calculation of hour .When the time taken exceeds h, you immediately return that val and prevent the overflow
I remember doing this question earlier but the way you taught I am confident I can now easily solve problems like these in interviews with a clear and intuitive explanation. Understood, thanks!
same
Thanks Striver, always struggled to understand the reason behind the answer being always the low value, now it's clear as crystal, all thanks to you❤❤
I have earlier solved the question but intuition of yours is truly amazing... Great Content 🔥🔥
The wait is finally over.... Thanks a ton striver❤
finally found when to return the low and when to return the value high
thanks to your intuition I could do this question on my own using the same approach that you explained in this video without any help! kudos
Hi Raj,
Both the BF and Optimal solutions will have an additional TC of O(n) to find the maximum element from the array.
If anyone was getting runtime error of integer overflow do change the datatype of totalhours to double or long long
logic is same as finding first occurance THANK YOU
Rather than using ceil we can use "sum = sum + (v[i] - 1)/ mid + 1;"
It's more optimal
what's the logic behind the (v[i]-1) ??
Can you explain the logic?
Understood! Wonderful explanation as always, thank you very very much for your effort!!
understood
Thank you striver for such an amazing explanation..
Got asked this question today!
Understood, Thanks striver for this amazing video.
while finding maximum element in an unsorted array it takes O(n) time so ultimately the time complexity of this question is O(n).
O(n*log(max) >>> O(n) :)
Thanks so much!! I was able to solve it without watching the video !!
public int findHours(int[] arr, int bananaCount) {
int totalHrs = 0;
for (int i = 0; i < arr.length; i++) {
totalHrs += Math.ceil((double) arr[i] / bananaCount);
}
return totalHrs;
}
Cast to double, because ceil here needs floating-point number.
Understood
Please do upload videos consistently 😊
Thank you striver....Understood everything🙂...keep up the good work
fr?
hey striver, I feel that there is some problem with the leetcode question. for the testcase [805306368, 805306368, 805306368] and h = 1000000000, the expected answer is k=3
when we use an ans variable to store the desired value of mid, the code gives output = 1 which is incorrect, however, when we simply return the low, the testcase passes.
I am not able to understand what is happening here. If this is a case of an overflow, I have already substitued long long. Pls help.
bool check(vector& piles,int h,int k){
long long ans=0;
for(int i=0;ih)return false;
}
//cout
@@thegame587 Thanks a lot buddy for replying, it's working now. I had figured the overflow problem :)
@@aniketgupta8064 you can also make the func dataype, totalH datatype to long, this can also works
@@jayant-baid thanks 👍
@@jayant-baid thank you bro i stuck in this problem for more than hour and you save me from it 😊😊
why i feel like i am watching these videos again
Solved this without watching the video myself
To reduce runtime one can use instead of ceil
ans += (piles[i]+k-1)/k;
You are just incredible ❤️🎉🎉
Thanks!
Hey striver, i am getting 1 test case wrong in this question, don't know why
i still tried with your own code , but it is not working, nearly 3 problems have been in this way,
any one please respond....
very helpful explaination
understood 😇
@striver thanks for explanation
Understood Very Well!
UNDERSTOOD;
i was doing this wrong for three hours and what i was doing wrong was only not applying double🙂
Understood!
The typecasted leet-code code:
#include
#include
#include
class Solution {
private:
int maxEl(vector& piles) {
int maxi = INT_MIN;
for (int i = 0; i < piles.size(); i++) {
maxi = max(maxi, piles[i]);
}
return maxi;
}
long long totEl(vector& piles, int mid) {
long long totH = 0;
int n = piles.size();
for (int i = 0; i < n; i++) {
totH += (piles[i] + mid - 1) / mid; // Updated calculation
}
return totH;
}
public:
int minEatingSpeed(vector& piles, int h) {
int low = 1;
long long high = maxEl(piles);
int ans = INT_MAX;
while (low
One doubt:
what if h = 5 and piles = [30,11,23,4,20]here if we take k greater than 30 then also we'll get the answer. Then how can we apply that brute force where we are taking range of k to be [1, greatest_element] in that array?
Understood, thank you.
nice explaination
koko needs to stop eating those bananas
Understood
understood
little explanation solve the whole question #include
using namespace std;
bool fun(vector & v,int h ,int &ans, int mid){
int sum=0;
for(int i=0;ih){
return true;
}
}
ans=mid;
return false;
}
int minimumRateToEatBananas(vector v, int h) {
int ma=INT_MIN;
for(int i=0;i
is max function doesn't take O(N) time
Koko for real is gonna shit the whole next day ! AWESOME VID STRIVER
Good explanation understood
Could you also please explain.Find K close elements with binary search.I've seen in some of the binary search approaches.Few of the solutions are with right=mid or left=mid.
Finding max will add O(n) to the time complexity.won't it?
Thank You
Best explaination😍
Koko needs to do fast for atleast one year .
Thank you bhaiya
ceil can be replaced with
x / a + ( (x % a) != 0 ? 1 : 0)
🔴Leetcode Solution:-
class Solution {
private:
int maxi(vector arr){
int ans = INT_MIN;
for(int i=0; i
Nice explanation ❤
Why does it not work if I take the minimum eating speed as the minimum of the array ?
I am using javascript😇
Test case 125 faiiled
out of 126
Understood✅🔥🔥
was waiting for this
Understood!!
why this solution still falls in binary search. where we create extra memory for lowest pile 1 to highest pile 11 to get maximum pile per hour?
why do you return low, you didn't explained that part
but if the array is sorted then we don't need to find max of array .. its just the last element of the array .. i guess
Understood sir 🫡🤍
striver is best
Leetcode solution all test cases passed :
class Solution {
public:
int findmaximum(vector &piles){
int n = piles.size();
int maxi = INT_MIN;
for(int i =0; i
so if an array is not sorted, can this logic still work, please tell
Yes it will work fine with the same code because our initial search space is [1, max(piles)] not the piles array
understand
Understood!!!!!
UNDERSTOOD
Following this series. Really helpfull 💪💪
For people doing on leetcode and getting error after testcase 120 ...just use long long hrtaken and also return long long..
Here's the code if someone needs it
class Solution {
public:
long long hrtaken(vector pi, int h) {
long long hr = 0;
for (auto i : pi) {
hr += ceil((double)i/(double)h);
}
return hr;
}
int minEatingSpeed(vector& piles, int h) {
int maxt = -1;
int m = -1;
for (auto i : piles)
m = max(m, i);
int low = 1, high = m;
while (low
how can we come to know that the given question is bs on answers.
understood
Understood
Hi striver, i am experience developer approx 5 years, my query is how to get calls from recruiters
you are 5 year of experience and asking questions like a freshers
It means from the year wise you are 5 years exp but experience/Knowledge wise you are fresher have no idea
9:54 at this while calculating time complexity of linear approach func will run for n times .but inside it ceil function will be used jiski time complexity log n hoti h so vo consider nahi krenge?
can we do this by finding sum of elements in array and getting the ceil value by dividing it with number of hours which takes o(N) time complexity which is better than binary search.
Understood:)
Understood :)
understood :)
By what time, will the whole A2Z course will be completed?
how to quickly understand that low is pointing to answer or high?
dry run by taking 1 example
how to tackle case of overflow in total hours calculated even if we use long long to calculate for total hours required it is giving wa?
use long long toatl hours instead of int
class Solution {
int ans=-1;
private int binarySearch(int[] piles,int h,int low,int high){
if(low>high){
return ans;
}
int mid = low+(high-low)/2;
if(findRequiredHours(piles,mid)
🔥
Kb tk playlist complete hogi?
Thanks++
was asked in de shaw
Its failing in last test case
use long long for totalhour data type every where
sir even after submitting the exactly same code as yours...its getting wrong on 10th test case
add this condition to prevent overflow while calculating totalHours required to eat for the current rate
if(timeReq > h){
break;
}
or use long long datatype every where
Can anyone explain why we have use double while using ceil function?
#include
using namespace std;
int main() {
int ans = ceil(4/(double)3);
cout
spent whole day in this problem still could not do it
but yh to sorted nhi to binary kese laga
search space is sorted bro, our answer doesn't lie isnide piles array, it lies inside the range [1, maxelement] which is sorted.
damn now I get it thanks brother
koko k tho maje hi maje
Uunderstood