A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

&nbsp;
Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.


Example 2:

Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4


Example 3:

Input: weights = [1,2,3,1,1], days = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1


&nbsp;
Constraints:


	1 &lt;= days &lt;= weights.length &lt;= 5 * 104
	1 &lt;= weights[i] &lt;= 500

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def calc(m):#function calculate no of days for given weight
            c,s=0,0
            for i in weights:
                if i+s>m:
                    c+=1
                    s=0
                s+=i
            if s>0:
                c+=1
            return c
        left,right=max(weights),sum(weights)
        while left <=right:
            mid = (left+right)//2
            if calc(mid) > days:
                left = mid+1
            else :
                right = mid -1
        return left
class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0;
        int right = 0;
        //  left is the biggest element in the array. It's set as the lower boundary.
        //  right is the sum of the array, which is the upper limit. 
        for (int weight : weights) {
            left = Math.max(weight, left);
            right += weight;
        }
        int res = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            // make sure mid is a possible value 
            if (isPossible(weights, days, mid)) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
    
    public boolean isPossible(int [] weights, int days, int mid) {
        int totalDays = 1;
        int totalWeight = 0;
        for (int i = 0; i < weights.length; i++) {
            totalWeight += weights[i];
            // increase totalDays if totalWeight is larger than mid
            if (totalWeight > mid) {
                totalDays++;
                totalWeight = weights[i]; 
            } 
            // the problem states all the packages have to ship within `days` days 
            if (totalDays > days) {
                return false;
            }
        }
        return true;
    }
    
}
class Solution {
public:
    // function to check if it is possible to ship all the items within the given number of days using a given weight capacity
    bool isPossible(int cp, vector<int>& weights, int days)
    {
        int d = 1;
        int cw = 0;
        // iterate through the weights and check if it is possible to ship all the items
        for (auto x : weights) {
            if (x + cw <= cp) {
                // if the current weight can be added to the current capacity, add it
                cw += x;
            } else {
                // if not, increment the number of days required for shipping and start a new shipment
                d++;
                cw = x;
                if (x > cp) {
                    // if the current weight is greater than the current capacity, it is impossible to ship all the items
                    return false;
                }
            }
        }
        // check if it is possible to ship all the items within the given number of days
        return d <= days;
    }
    
    // function to find the minimum weight capacity required to ship all the items within the given number of days
    int shipWithinDays(vector<int>& weights, int days)
    {
        // initialize the search range for the weight capacity
        int s = 1;
        int e = 1E9;
        int ans = -1;
        
        // perform binary search on the weight capacity range
        while (s <= e) {
            // set the mid-point of the range as the current weight capacity
            int mid = (s + e) / 2;
            
            // check if it is possible to ship all the items within the given number of days using the current weight capacity
            bool ok = isPossible(mid, weights, days);
            
            // if it is possible to ship all the items within the given number of days using the current weight capacity,
            // set the current weight capacity as the new answer and reduce the upper bound of the weight capacity range
            if (ok) {
                ans = mid;
                e = mid - 1;
            } else {
                // if it is not possible to ship all the items within the given number of days using the current weight capacity,
                // increase the lower bound of the weight capacity range
                s = mid + 1;
            }
        }
        
        // return the minimum weight capacity required to ship all the items within the given number of days
        return ans;
    }
};
/**
 * @param {number[]} weights
 * @param {number} days
 * @return {number}
 */
var shipWithinDays = function(weights, days) {
    // set left as max of weight, set right as sum of weight
    let left = Math.max(...weights), right = weights.reduce((a, b) => a + b);

    // max weight cannot exceed the capacity of ship
    while (left < right) {
        // set middle weight
        const m = Math.floor((left + right) / 2);
        // reset weight if can be load
        can(m) ? (left = m + 1) : (right = m);
    }

    // result
    return left;

    // check if load can be
    function can(v) {
        let need = 1, current = 0;

        for (let i of weights) {
            if (current + i > v) {
                need++;
                current = i;
            }
            else {
                current += i;
            }
        }

        return need > days;
    }
};
Capacity To Ship Packages Within D Days