Shortest+sweetest solution


#1

Using binary search. I will approach to the solution gradually. Scroll to the last if you just wanna see the solution quickly.

Understand that binary search is just a fast way to do trial and error. If value is too low to be a possible answer, try bigger value. If value is too high, try smaller value.

Use binary search because it saves you from hassling with complicated calculations. Now luckily the time constraints were easy to do binary search. If the time constraints were stricter, you will have to do the calculation manually (as done in the official solutions) instead of doing the trial and error(using binary search).

Here we go:

  • In all problems of binary search, first think of target. Our target is to find maximum possible number of fruit basket.

  • Binary search is trial and error. So you will want to set the range of numbers you want to try and check. int left, and int right are used to defined the lower limit and upper limit of the range.

  • Decide the value of left (lower limit of target(target=no of fruit baskets) = 0)

  • Decide the value of right(upper limit of target(target = no of fruit baskets) = explained below how to find this).

Explanation to find upper limit of number of fruit baskets
You can use possible upper limits. It can be right = a or right = b or right = a + 2b or right = 2a + 3b. But higher values will take more time to execute.
But if you think smartly, the number of baskets cannot exceed the value of a and b.
so right < a and right < b. So we decide to set the value of right = min(a,b).

So far I have covered and variables required to setup the binary search. Now i will discuss the process.

  • Lets say mid = (left + right)/2
    So we are trying mid number of baskets , and see if it possible.

  • If there are mid baskets, this means there are a apples, b bananas already inside them. So each basket already has 1 banana, 1 apple. Now the remaining apples bananas and cherries left are a-mid, b-mid, and c.

  • These remaining fruits must fill all the baskets such that all baskets have 3 fruits. Since all baskets already have 2 fruits (1 banana and 1 apple), We need 1 extra fruit per basket.
    if(a-mid+b-mid+c>=mid && a1>=0 && b>=0)
    {
    low=mid+1;
    ans=mid;
    }

  • So the condition is fruits left(a-mid + b-mid + c) >= fruits needed (mid).

  • If this condition is satisfied, that means these number of baskets are possible to exist. Since we need max no of baskets, lets try higher number of baskets (low = mid + 1). This means set the trial and error range to mid + 1 to right.

  • If condition is not satisfied, try lower values. high = mid-1 does this.
    Posting the entire code for reference.

    if(a==0 || b==0)
    return 0;

  • Dont forget these base cases mentioned above.

    int low=1, high=min(a,b),ans=0;
    while(low <= high)
    {
    int mid=low+(high-low)/2;
    int a1=a-mid, b1=b-mid;
    if(a1+b1+c>=mid && a1>=0 && b>=0)
    {
    low=mid+1;
    ans=mid;
    }
    else
    high=mid-1;

    }
    return ans;

Sorry for the indendation issues, i tried figuring out but to vain.

If you liked my effort, please give me an endorsement in C++ and algorithms on my LikedIn Profile:
https://www.linkedin.com/in/piyush-soni-18490616a/