A conveyor belt has packages that must be shipped from one port to another within D days.
The i-th 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 D days.
 
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 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], D = 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], D = 4
Output: 3
Explanation: 
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

 
Constraints:

1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

Difficulty: interview

Starter code:

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        

Solutions:
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = left * len(weights) // D
        while left < right: 
            mid = left + (right - left) // 2
            c = 0 
            d = 1 
            for w in weights:
                if c + w <= mid:
                    c += w
                else:
                    d += 1
                    c = w
            if d > D:
                left = mid + 1
            else:
                right = mid
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        #binary search, check capacity every time
        def checkCapacity(cap: int, weights: List[int], D: int):
            val = 0
            res = 1
            for w in weights:
                val += w
                if val > cap:
                    res += 1
                    val = w
            return res <= D
        
        low = max(weights)
        high = min(sum(weights), low*len(weights)//D)
        
        while low < high:
            mid = (low + high)//2
            if checkCapacity(mid,weights,D):
                high = mid
            else:
                low = mid+1
        return high
    
    
    
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def canShip(capacity: int) -> bool:
            nonlocal D
            count = 1
            curcap = 0 
            for w in weights:
                if curcap + w <= capacity:
                    curcap += w
                else:
                    count += 1
                    curcap = w
            return count <= D
            
        
        max_weight = max(weights)
        lo = sum(weights) // D
        hi = max_weight * (len(weights) // D + 1)
        while lo < hi:
            mid = (lo + hi) // 2
            if mid < max_weight or not canShip(mid):
                lo = mid + 1
            else:
                hi = mid
        return lo
                


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        start = max(weights)
        end = sum(weights)
        while start < end:
            mid = start + (end - start)//2
            print(mid)
            counter = 0
            summation = 0
            for i in weights:
                if summation+i==mid:
                    counter += 1
                    summation = 0
                elif summation+i>mid:
                    counter+= 1
                    summation = i
                elif summation<mid:
                    summation += i
            counter += 1
            print(counter)
            if counter >D: start = mid+1
            else: end = mid
        return start

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        lo = 0 
        hi = 0
        for i in range(len(weights)):
            lo = max(lo,weights[i])
            hi = hi + weights[i]
        
        optimalcapacity =hi+1
        while lo<=hi:
            days =1
            capacity = 0
            mid = lo + (hi - lo)//2
            for i in range(len(weights)):
                if weights[i] + capacity > mid:
                    days= days+1
                    capacity = weights[i]
                else:
                    capacity+=weights[i]
            if days <= D:
                hi = mid -1
                optimalcapacity= min(optimalcapacity,mid)
            else:
                lo = mid+1
        return optimalcapacity        
            
            
            


def find(w,m,d,l):
    s =0
    c =1
    for i in range(l):
        s+=w[i]
        if s>m:
            s =w[i]
            c+=1
        if c>d:
            return False
    return True
        

class Solution:
    def shipWithinDays(self, w: List[int], D: int) -> int:
        l =len(w)
        s = max(w)      
        e = sum(w)
        m = s+(e-s)//2
        p =0
        while s<=e:
            a = find(w,m,D,l)
            if a == True:
                p =m
                e =m-1
                m = s+(e-s)//2
            else:
                s = m+1
                m = s+(e-s)//2
        return p

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        #Lower bound has to be the maximum of the weight to ship all weights
        #Upper bound is the sum of the weights (can ship all packages in one day)
        left= max(weights)
        right =sum(weights)
        
        #Finding a weight which is between lower and upper value
        while left <= right:
            
            #days_needed helps to calculate how many days can be covered with the weight chosen
            #cur tells us the sum of all the weights for the day
            mid, days_needed, cur = int((left + right) / 2), 1, 0 
            
            #mid is the weight which is chosen to divide all the other wirghts in days
            #loop through each weight
            for w in weights:
                if cur + w > mid:
                    days_needed += 1
                    cur = 0
                cur += w
                
            if days_needed > D: 
                left = mid + 1
                
            else: 
                right = mid-1
                
        return left #why is left returned? anything can be returned whether its left or right

def possible(weights, cap, D):
    if cap <= 0:
        return False
    c = 1
    cur = 0
    for w in weights:
        if cur + w <= cap:
            cur += w
        elif w <= cap:
            c += 1
            cur = w
        else:
            return False
    print(c, cap)
    return c <= D

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        hi, lo = sum(weights), max(weights)
        mid = (hi + lo)//2
        while lo <= hi:
            print(lo, hi, mid)
            p = possible(weights, mid, D)
            if p and not possible(weights, mid-1, D):
                return mid
            elif not p:
                lo = mid +1
            else:
                hi = mid
            mid = (hi+lo) // 2
        return -1

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        def possible(c):
            ship = 1
            cargo = 0
            for i in range(len(weights)):
                if ship > D:
                    return False
                if (cargo + weights[i]) > c:
                    ship += 1
                    cargo = weights[i]
                else: 
                    cargo += weights[i]
            return ship <= D
        
        right = sum(weights)

        while left <= right:
        
            mid = floor((left + right)/2)
            if possible(mid):
                if left == mid:
                    break
                right = mid
            else:
                left = mid + 1
        print(left, right, mid)
        return mid

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def test_ship_weights(capacity):
            dq = collections.deque(weights)
            for day in range(D):
                daily_capacity = capacity
                while dq and dq[0] <= daily_capacity:
                    daily_capacity -=  dq.popleft()
                
            if dq: return False
            else: return True
            
        l, r = 0, sum(weights)
        
        while l<r:
            m = (l+r) //2 + 1
            if test_ship_weights(m):
                r = m-1
            else:
                l = m+1
        if test_ship_weights(l): return l
        if test_ship_weights(r): return r
        if test_ship_weights(m): return m
        else:
            return r + 1
        # val = test_ship_weights(l)
        # if val==False: 
        #     if test_ship_weights(r): 
        #         return r
        return l
        

        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        #Lower bound has to be the maximum of the weight to ship all weights
        #Upper bound is the sum of the weights (can ship all packages in one day)

        left, right = max(weights), sum(weights)
        while left < right:
            mid, need, cur = int((left + right) / 2), 1, 0
            for w in weights:
                if cur + w > mid:
                    need += 1
                    cur = 0
                cur += w
            if need > D: left = mid + 1
            else: right = mid
        return left

class Solution:
    
    def isPossible(self, ship_weight: int, d:int) -> bool:
        i = 0
        ships = 0
        curr_w = 0
        while i < len(self.weights):
            if (ship_weight - curr_w) < self.weights[i]:
                curr_w = 0
                ships += 1
                if ship_weight < self.weights[i] or ships >= d:
                    return False
            curr_w += self.weights[i]
            i += 1
        return True
    
    def shipWithinDays(self, weights: List[int], d: int) -> int:
        self.weights = weights
        min_w = math.ceil(sum(weights)/d)
        max_w = max(weights) * math.ceil(len(weights) / d) + 1 # may be sub-optimal choice
        
        while True:
            mid_w = min_w + (max_w - min_w)//2
            if self.isPossible(mid_w, d):
                if not self.isPossible(mid_w-1, d):
                    return mid_w
                max_w = mid_w
            else:
                min_w = mid_w
        return 0 # not possible


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        average = sum(weights) // len(weights)
        min_capacity = max(max(weights), average)
        
        min_w = min_capacity
        max_w = min_w * 2
        while not enought_capacity(max_w, weights, D):
            min_w = max_w
            max_w = max_w * 2
        
        while True:              
            mid = min_w + (max_w - min_w) // 2
            if enought_capacity(mid, weights, D):
                if mid == min_w or mid == max_w:
                    return mid
                max_w = mid
            else:
                min_w = mid + 1
                
 #       10 11 12 13 14 15
        
    
def enought_capacity(capacity: int, weights: List[int], D: int):
    remain_ships = D - 1
    sum_weight = 0
    for pck_weight in weights:
        sum_weight += pck_weight
        if sum_weight > capacity:
            remain_ships -= 1
            sum_weight = pck_weight
            
    if remain_ships >= 0:
        return True
    return False
        
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        #eights.sort()
        left = max(weights)
        right = sum(weights)
        
        def counter(limit):
            curr = 0
            count = 0
            for w in weights:
                if curr+w==limit:
                    count+=1
                    curr =0
                elif curr+w > limit:
                    count += 1
                    curr = w
                else:
                    curr += w
            return count if curr==0 else count+1
        
        res = right
        while left <=right:
            mid = (left+right)//2
            
            val = counter(mid)
            if val <=D:
                res = min(res,mid)
                right=mid-1
                
            else:
                left=mid+1
                #ight=mid-1
        return res


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def test_ship_weights(capacity):
            dq = collections.deque(weights)
            for day in range(D):
                daily_capacity = capacity
                while dq and dq[0] <= daily_capacity:
                    daily_capacity -=  dq.popleft()
                
            if dq: return False
            else: return True
            
        l, r = 0, sum(weights)
        
        while l<r:
            m = (l+r) //2 + 1
            if test_ship_weights(m):
                r = m-1
            else:
                l = m+1
        if test_ship_weights(l): return l
        if test_ship_weights(r): return r
        if test_ship_weights(m): return m
        else:
            return r + 1

        return l
        

        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def test_ship_weights(capacity):
            dq = collections.deque(weights)
            for day in range(D):
                daily_capacity = capacity
                while dq and dq[0] <= daily_capacity:
                    daily_capacity -=  dq.popleft()
                
            if dq: return False
            else: return True
            
        l, r = max(weights), sum(weights)
        
        while l<r:
            m = (l+r) //2 
            if test_ship_weights(m):
                r = m
            else:
                l = m+1

        return l
        

        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        lower = min(weights)
        upper = sum(weights)
        
        while lower < upper:
            mid = (lower + upper) // 2
            if self.check(weights, D, mid):
                upper = mid
            else:
                lower = mid + 1
                
        return lower
    
    def check(self, weights, D, cap):
        s = weights[0]
        ct = 1
        if s > cap:
            return False
        
        for x in weights[1:]:
            if x > cap:
                return False
            if s + x <= cap:
                s += x
            else:
                s = x
                ct += 1
        return ct <= D

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        def possible(c):
            ship = 1
            cargo = 0
            for i in range(len(weights)):
                if ship > D:
                    return False
                if (cargo + weights[i]) > c:
                    ship += 1
                    cargo = weights[i]
                else: 
                    cargo += weights[i]
            return ship <= D
        
        right = sum(weights)

        while left <= right:
            mid = floor((left + right)/2)
            if possible(mid):
                if left == mid:
                    break
                right = mid
            else:
                left = mid + 1
        return mid

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        
        def isvalid(mid):
            
            total=0
            package=1
            for weight in weights:
                if weight>mid:
                    return False
                total+=weight
                if total>mid:
                    package+=1
                    total=weight
            return package<=D
                
        
        def binsearch(low,high):
            
            while low<high:
                mid = low + (high-low)//2
                print(isvalid(mid),mid)
                if not isvalid(mid) :
                    low=mid+1
                else:
                    high=mid
            return low
        
        return binsearch(0,sum(weights))

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left, right = max(weights), sum(weights)
        
        def condition(m):
            days = 0
            cap = m
            n = len(weights)
            i = 0
            while(i<n):
                w = weights[i]
                if(m-w>=0):
                    m -= w
                    i +=1
                else:
                    days += 1
                    m = cap -w
                    i +=1
                if(days>D):
                    return False
            days +=1
            if(days>D):
                return False
            return True
                    
        while left<right:
                mid = left+ (right-left)//2
                if(condition(mid)):
                    right = mid
                else:
                    left=mid+1
        return left
        
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def helper(c):
            s = 0
            d = 1
            for w in weights:
                s += w
                if s > c:
                    d += 1
                    s = w
                    if d > D:
                        return False
            return True
        l = max(weights)
        r = sum(weights)
        while l < r:
            m = l + (r-l)//2
            if helper(m):
                r = m
            else:
                l = m + 1
        return l

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        lo, hi = max(weights), sum(weights)   
        while lo < hi:
            mid = (lo + hi) // 2
            tot, res = 0, 1
            for wt in weights:
                if tot + wt > mid:
                    res += 1
                    tot = wt
                    # print(\"res\", res)
                    
                else:
                    tot += wt
            if res <= D:
                hi = mid
                # print(\"hi\",hi)
            else:
                lo = mid+1
                # print(\"lo\",lo)
        return lo

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        lo = max(weights)
        hi = sum(weights)
        
        def calculate_capacity(n):
            num_day = 1
            curr_capacity = 0
            for weight in weights:
                if curr_capacity + weight <= n:
                    curr_capacity += weight
                else:
                    num_day += 1
                    curr_capacity = weight
            return num_day
        
        while lo < hi:
            mid = lo + (hi - lo) // 2
            day = calculate_capacity(mid)
            if day > D:
                lo = mid + 1
            else:
                hi = mid
        return lo


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = left * len(weights)//D

        def checkShipping(cap):
            # check whether we can ship all packages in D days
            days = 1
            onboard = 0
            for i, v in enumerate(weights):
                if onboard + v > cap:
                    days += 1
                    onboard = v
                else:
                    onboard += v

                if days > D:
                    return False
            return True

        #ans = right
        while left < right:
            mid = left + (right-left) // 2
            if checkShipping(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        # dp [i][d]
        # dp [0][d] = w [0]
        # dp [i][d] = max (w [i], dp [i-1][d-1]) 
        #             min (dp [i-j][d-1] + sum (w [j: i]))
        # dp [i][d] = max (
        #                 min (
        #                   dp [i-j][d-1] + sum (w [i-j+1: i+1]) ,   j >= 1    
        #                 ))
        # O (n*n*D)
        
        # binary search 
        # O (n log n)
        
        n = len (weights)
        def canShipWithCap (cap):
            d = 1
            w = 0
            for i in range (0, n):
                if weights [i] + w <= cap:
                    w += weights [i]
                else: 
                    w = weights [i]
                    d += 1
                    if d > D: return False
            return True
        
        high = sum (weights)
        low = max (weights)
        
        while low < high:
            
            mid = low + (high - low) // 2
            if canShipWithCap (mid): high = mid 
            else: low = mid + 1
            
        return low
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        if D == 1:
            return sum(weights)
        start = max(max(weights),-(-sum(weights)//D))
        end = sum(weights)
        n = len(weights)
        def validate(x):
            count = 0
            i = 0
            cur = 0
            while count < D:
                while i< n and cur <= x:
                    cur += weights[i]
                    i += 1
                if i == n and cur <= x:
                    return True
                cur = weights[i-1]
                count += 1
            return False

        while start < end:
            m = (start+end)//2
            if validate(m):
                end = m
            else:
                start = m+1
        return start
            
            


from collections import defaultdict
class Solution:
     def canShipWithinDays(self, weights: List[int], D: int, maxWeight: int) -> bool:
        if max(weights) > maxWeight:
            return False
        
        shipmentweights = [0]
        for w in weights:
            if shipmentweights[-1] + w <= maxWeight:
                shipmentweights[-1] += w
            else:
                shipmentweights.append(w)
        return len(shipmentweights) <= D
    
     def shipWithinDays(self, weights: List[int], D: int) -> int:
        maxweight = sum(weights)
        minweight = max(weights)
        while maxweight > minweight + 1:
            mw = (maxweight + minweight) // 2 
            if self.canShipWithinDays(weights, D, mw):
                maxweight = mw
            else:
                minweight = mw
        if self.canShipWithinDays(weights, D, minweight):
            return minweight
        else:
            return maxweight

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = sum(weights)
        
        def possible_with_capacity(c):
            days = 1
            total = 0
            for weight in weights:
                total += weight
                if total > c:
                    total = weight
                    days += 1
                    if days > D:
                        return False
            return True
        
        while left < right:
            cap = left + (right-left)//2
            if possible_with_capacity(cap):
                right = cap
            else:
                left = cap + 1
        
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        maxVal = weights[0]
        sum = 0
        for weight in weights:
            if maxVal < weight:
                maxVal = weight
            sum += weight
        if D == len(weights):
            return maxVal
        if D == 1:
            return sum

        def validWeight(weight_try: int) -> bool:
            count = 0
            local_sum = 0
            for weight in weights:
                local_sum += weight
                if local_sum > weight_try:
                    local_sum = weight
                    count += 1
            return count < D

        left = maxVal
        right = sum
        result = 0
        while left <= right:
            mid = (left + right) // 2
            if validWeight(mid):
                result = mid
                right = mid - 1
            else:
                left = mid + 1
        return result

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def days_required(t):
            running_sum = 0
            days = 0
            for i in range(n):
                running_sum += weights[i]
                if running_sum > t:
                    days += 1
                    running_sum = weights[i]
                    
            return days
        
        
        n = len(weights)
        lo, hi = max(weights), sum(weights)
        while(lo <= hi):
            capacity = (lo+hi)//2
            
            if days_required(capacity) < D:
                hi = capacity -1
            else:
                lo = capacity +1
                
                
        return lo
            


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def canShip(maxCapacity):
            days = 0
            cur = 0
            for w in weights:
                if cur + w <= maxCapacity:
                    cur += w
                else:
                    cur = w
                    days += 1
            days += 1
            return days <= D
        
        l = max(weights)
        r = sum(weights)
        
        while l < r:
            mid = (l + r) // 2
            if canShip(mid):
                r = mid
            else:
                l = mid+1
        return l

# +60
# +30
# +30
# did not get this one, found the solution in forums
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        min_cap = max(weights)
        max_cap = sum(weights)
        
        while min_cap < max_cap:
            cap = (min_cap + max_cap) // 2
            
            remainder = cap
            days = 1
            
            for i in range(len(weights)):
                if weights[i] > remainder:
                    remainder = cap
                    days += 1
                    
                remainder -= weights[i]
                
            if days > D:
                min_cap = cap + 1
            else:
                max_cap = cap
                
        
        return min_cap

class Solution:
    def check(self, w, cap, D):
            c = 0
            d = 0
            i = 0
            while(i<len(w)):
                c+=w[i]
                if c>cap:
                    d += 1
                    c = w[i]
                i+=1
            return d
        
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l , h= max(weights), sum(weights)
        while(l<=h):
            m = (l+h)//2
            if self.check(weights, m, D)>=D:
                l = m + 1
            else:
                h = m - 1
        return l 


import math

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        sum_ = sum(weights)
        max_weight = max(weights)
        if D == 1:
            return sum_
        
        def check_capacity_enough(weights, D, capac):
            temp_cargo = 0
            count_ships = 1
            for i in range(len(weights)):
                if temp_cargo + weights[i] <= capac:
                    temp_cargo += weights[i]
                else:
                    count_ships += 1
                    if count_ships > D:
                        return False
                    temp_cargo = weights[i]
            return True
        
        def binary_search(weights, D, sum_, max_weight):
            left = max(math.floor(sum_/D) - 1, max_weight-1) 
            right = max(math.ceil(2*sum_/D)+1, max_weight+3) 
            while right-left >= 2:
                mid = (left + right)//2
                if mid >= max_weight and check_capacity_enough(weights, D, mid):
                    right = mid
                else:
                    left = mid
            return right
        
        return binary_search(weights, D, sum_, max_weight)

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def condition(capacity):
            day = 1
            increaseCap = 0
            i=0
            while i < len(weights):
                increaseCap +=weights[i]
                if increaseCap > capacity:
                    increaseCap = weights[i]
                    day+=1
                    if day > D: return False
                i+=1
            return True 
        
        left , right  = max(weights), sum(weights)
        while left < right:
            mid =  left + (right - left) //2
            if condition(mid):
                right = mid
            else:
                left = mid+1
        return left


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def checkDays(capacity): 
            days =  1
            cc = 0 
            for num in weights: 
                if cc == capacity: 
                    cc = 0 
                    days +=1 
                if num > capacity:
                    return 999999
                cc += num 
                if cc > capacity: 
                    days +=1 
                    cc = num 
            return days 
        hi = max(weights) * len(weights)
        low = 0 
        while low < hi: 
            guess = int((low + hi)/2)
            print(low, hi,guess)
            d = checkDays(guess)
            if d > D: 
                low = guess + 1
            else:
                hi = guess
        return low

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def canCarry(cap):
            cur,d = 0, 1
            for w in weights:
                if w > cap: return False
                cur += w
                if cur > cap:
                    cur = w
                    d += 1
                if d > D: return False
            return cur <= cap
        
        l, r = max(weights), sum(weights)
        while l < r:
            m = (l + r) // 2
            if canCarry(m): r = m
            else: l = m + 1
        return l

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        n = len(weights)
        left = 1
        right = sum(weights)
        
        def works(capacity):
            tot_days = 0
            i = 0
            
            while i < n:
                j = i
                curr_load = 0
                
                while j < n and curr_load + weights[j] <= capacity:
                    curr_load += weights[j]
                    j += 1
                    
                if j == i:
                    return False
                
                i = j
                tot_days += 1
                
            return tot_days <= D
            
        while left <= right:
            mid = (left + right) // 2
            
            if works(mid):
                right = mid - 1
            else:
                left = mid + 1
        
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        total = sum(weights)
        lo,hi = max(max(weights),total//D), total
        n=len(weights)
        def valid(x):
            i = days = 0
            while i < n:
                S=0
                while i<n and S+weights[i]<=x:
                    S+=weights[i]
                    i+=1
                days+=1
            return days<=D
        
        while lo<hi:
            mid = (lo+hi)//2
            print(mid)
            if valid(mid):
                hi=mid
            else:
                lo=mid+1
        return lo
                    


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        
        def isvalid(mid):
            
            total=0
            package=1
            for weight in weights:
                if weight>mid:
                    return False
                total+=weight
                if total>mid:
                    package+=1
                    total=weight
            return package<=D
                
        
        def binsearch(low,high):
            
            while low<high:
                mid = low + (high-low)//2
                print(isvalid(mid),mid)
                if not isvalid(mid) :
                    low=mid+1
                else:
                    high=mid
            return low
        
        return binsearch(max(weights),sum(weights))

class Solution:
  def shipWithinDays(self, weights: List[int], D: int) -> int:
    left, right = max(weights), sum(weights)
    while left < right:
      mid, need, cur = left + (right - left) // 2, 1, 0
      for w in weights:
        if cur + w > mid:
          need += 1
          cur = 0
        cur += w
      if need > D: left = mid + 1
      else : right = mid
    return left     


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l,r=max(weights),sum(weights)
        
        while l<r:
            mid=(l+r)//2
            cnt=1
            cursum=0
            for weight in weights:
                if cursum+weight<=mid:
                    cursum+=weight
                else:
                    cnt+=1
                    cursum=weight
            
            if cnt<=D:
                r=mid
            else:
                l=mid+1
            
        return r


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        if not weights:
            return 0
        
        NUM_PACKAGES = len(weights)
        if NUM_PACKAGES == 1:
            return weights[0]
        elif NUM_PACKAGES == 2:
            return max(weights[0], weights[1])
        
        max_capacity, min_capacity = 0, 0
        for weight in weights:
            max_capacity += weight
            min_capacity = weight if weight > min_capacity else min_capacity
        
        def possible(capacity):
            curr_weight = 0
            curr_days = 0
            package_index = 0
            
            while package_index < NUM_PACKAGES:
                
                if curr_weight + weights[package_index] > capacity:
                    curr_days += 1
                    
                    # print(capacity, curr_weight, weights[package_index], curr_days)
                    
                    # Too many days with this capacity
                    if curr_days > D:
                        return False
                    
                    curr_weight = 0
                    
                curr_weight += weights[package_index]
                package_index += 1
            
            curr_days += 1
            if curr_days > D:
                return False
            
            return True
        
        least_capacity = 0
        while min_capacity <= max_capacity:
            mid_point = (min_capacity + max_capacity) // 2
            if possible(mid_point):
                least_capacity = mid_point
                max_capacity = mid_point - 1
            else:
                min_capacity = mid_point + 1
            
            # print(\"Main:\", mid_point, min_capacity, max_capacity, least_capacity)
        
        return least_capacity


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:

        def package(weights, limit):    
            kk = 0
            count = 1
            for i in range(len(weights)):
                kk = kk + weights[i]

                if kk > limit:    
                    kk = weights[i]
                    count = count + 1

            return count
                
        lindex = max(weights)
        rindex = lindex * len(weights) // D

        while (lindex < rindex):

            mid = lindex + (rindex - lindex)//2

            capacity = mid
            Dstar = package(weights, capacity)

            if Dstar > D:
                lindex = mid + 1
            else:
                rindex = mid 

            
        return lindex

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        lo, hi = 0, 9999999
        ans = -1
        N = len(weights)
        
        for w in weights:
            lo = max(lo , w)
        
        def poss(val):
            n, cnt , sum = 0, 1, 0
            
            while n < N:
                if sum + weights[n] <= val:
                    sum += weights[n]
                else:
                    cnt += 1
                    sum = weights[n]
                n += 1
                
            return cnt
        
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            nn = poss(mid)
            if nn <= D:
                ans = mid
                hi = mid - 1
            else:
                lo = mid + 1
        
        return ans


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l = max(weights)
        r = 10**9
        
        while l < r:
            m = l + (r - l) // 2
            # now check if we use this m as the weight capacity for ship how many days we need
            days = 1
            s = 0
            for i in range(len(weights)):
                if s + weights[i] > m:
                    days += 1
                    s = weights[i]
                else:
                    s += weights[i]
                    
            if days <= D:
                r = m
            else:
                l = m + 1
        
        return l

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def countDays(weights, capacity):
            l, r, cnt, sumv = 0, 0, 0, 0
            while r < len(weights):
                sumv += weights[r]
                if sumv > capacity:
                    cnt += 1
                    l = r
                    sumv = 0
                else:
                    r += 1
            if sumv:
                cnt += 1
            return cnt
        maxv, sumv = max(weights), sum(weights)
        left, right = maxv, sumv
        while left < right:
            mid = (left + right) // 2
            days = countDays(weights, mid)
            if days > D:
                left = mid + 1
            else:
                right = mid
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left, right = max(weights), sum(weights)
        while left < right:
            mid = (left+right)//2
            if self.can_achieve(weights, mid, D):
                right = mid 
            else:
                left = mid+1 
                
        return left 
    
    def can_achieve(self, weights, max_weight, D):
        i = 0 
        total = 0
        days = 0
        while i < len(weights):
            if total + weights[i] > max_weight:
                total = 0
                days += 1
            total += weights[i]
            i += 1 
            
        days += 1 
        return days <= D
            
                
            
            
                


class Solution:
    def trips(self,l,c):
        currSum = 0
        t,i=0,0
        n = len(l)
        while(i<n):
            if(currSum+l[i]>c):
                currSum=0
                t =t+1
            else:
                currSum=currSum+l[i]
                i=i+1
        return t+1
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        low = max(weights)
        high = sum(weights)
        while(low<high):
            mid = int(low+(high-low)/2)
            if(self.trips(weights,mid)<=D):
                high = mid
            else:
                low = mid+1
        return low
                


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        # Binary search
        if not weights:
            return 0
        left, right = max(weights), sum(weights)
        while left < right:
            mid = left + (right - left) // 2
            if self.checkValidPartition(weights, mid, D):
                right = mid
            else:
                left = mid + 1
        return left
    
    def checkValidPartition(self, weights, capacity, D):
        count = 1
        cur_sum = 0
        for w in weights:
            if cur_sum + w > capacity:
                count += 1
                cur_sum = 0
            cur_sum += w
        return count <= D

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left, right = max(weights), sum(weights)
        while left < right:
            mid, need, cur = (left + right) / 2, 1, 0
            for w in weights:
                if cur + w > mid:
                    need += 1
                    cur = 0
                cur += w
            if need > D: left = mid + 1
            else: right = mid
        return int(left)
            


class Solution:
    def shipWithinDays(self, weights, D: int) -> int:
        if not weights or not D:
            return 0

        lo, hi = max(weights), sum(weights)
        ans = 0
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            res = self.validate(weights, D, mid)
            if res == 1:
                ans = mid
                hi = mid-1
            else:
                lo = mid+1
        return ans

    def validate(self, weights, D, capacity):
        count = 0
        w = 0
        D -= 1
        while w < len(weights):
            if count + weights[w] <= capacity:
                count += weights[w]
            else:
                count = weights[w]
                D -= 1
                if D < 0:
                    break
            w += 1
        if w == len(weights):
            return 1
        else:
            return -1



class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        hlim = sum(weights)
        llim = max(weights)
        def isValid(cap, days):
            temp = 0
            x = 0
            while x < len(weights):
                temp += weights[x]
                if temp > cap:
                    x -= 1
                    temp = 0
                    days -= 1
                x += 1
            return days >= 1
        ans = -1
        while llim <= hlim:
            mid = (llim+hlim)//2
            if isValid(mid, D):
                ans = mid
                hlim = mid-1
            else:
                llim = mid+1
        return ans

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l,r=max(weights),sum(weights)
        while(l<r):
            m,n,c=(l+r)/2,1,0
            for z in weights:
                if c+z>m:
                    n+=1
                    c=0
                c+=z
            if n>D:
                l=m+1
            else:
                r=m
        return int(l)
        '''left, right = max(weights), sum(weights)
        while left < right:
            mid, need, cur = (left + right) / 2, 1, 0
            for w in weights:
                if cur + w > mid:
                    need += 1
                    cur = 0
                cur += w
            if need > D: left = mid + 1
            else: right = mid
        return left'''

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:

        def package(weights, limit):    
            kk = 0
            count = 1
            for i in range(len(weights)):
                kk = kk + weights[i]

                if kk > limit:    
                    kk = weights[i]
                    count = count + 1

            return count
                
        lindex = max(weights)
        rindex = lindex * len(weights) // D

        while (lindex < rindex):

            mid = lindex + (rindex - lindex)//2
            
            Dstar = package(weights, mid)

            if Dstar > D:
                lindex = mid + 1
            else:
                rindex = mid 
            
        return lindex

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        left = max(weights)
        right = sum(weights) + 1
        
        
        while left < right:
            mid = left + (right-left)//2
            legal = self.evaluate(weights, D, mid)
            
            if legal:
                right = mid
            else:
                left = mid + 1
                
        return left
            
            
    def evaluate(self, weights, D, weight_capacity):
        cursum = 0
        days = 0
        for val in weights:
            if val > weight_capacity:
                return False
            if val + cursum > weight_capacity:
                days += 1
                cursum = val
            else:
                cursum += val
                
        if cursum != 0:
            days += 1
        
        if days > D:
            return False
        return True

class Solution:
    def canShipAllPackages(self, weight_capacity, D, weights):
        # print(f\"weight_capacity: {weight_capacity}\")

        days_needed = 1
        current_day_weight = 0
        i = 0
        while i < len(weights):
            weight = weights[i]
            # print(f\"weight: {weight}\")
            if (current_day_weight + weight) <= weight_capacity:
                current_day_weight += weight
                # print(f\"Day {days_needed}, current_day_weight: {current_day_weight}\")
                i += 1
            else:
                # print(f\"Too much! Next day work\")
                current_day_weight = 0
                days_needed += 1
                
        # print(\"f{days_needed}\")
        return days_needed <= D
        
        
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        if len(weights) == 0:
            return 0

        left = max(weights)
        right = sum(weights)
        
        while left < right:
            mid = (left + right) // 2
            if self.canShipAllPackages(mid, D, weights):
                right = mid
            else:
                left = mid + 1
                
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        n = len(weights)
        
        def count(c: int) -> int: 
            ans = 1
            curr = weights[0]
            for i in range(1, n): 
                if curr + weights[i] > c: 
                    ans += 1
                    curr = weights[i]
                else: 
                    curr += weights[i]
            return ans
        
        l = max(weights)
        r = sum(weights)
        while l < r: 
            m = (l + r) // 2
            if count(m) > D: 
                l = m + 1
            else: 
                r = m
        return l


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        minCapacity, maxCapacity = max(weights), sum(weights)
        
        while minCapacity < maxCapacity:
            capacityCandidate = (minCapacity + maxCapacity) // 2
            daysToShip, currentCargo = 1, 0
            
            for newCargo in weights:
                if currentCargo + newCargo > capacityCandidate:
                    currentCargo = 0
                    daysToShip += 1
                currentCargo += newCargo
            
            if daysToShip <= D:
                maxCapacity = capacityCandidate
            else:
                minCapacity = capacityCandidate + 1
        
        return minCapacity

class Solution:
    def get_day(self, weights, cap):
        i = 0
        res = 0
        wei = 0
        while i < len(weights): 
            if wei + weights[i] <= cap:
                    wei += weights[i]
                    i += 1
            else:
                wei = 0
                res += 1
        return res + 1
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        
        start, end = max(weights), sum(weights)
        
        while start < end:
            mid = (start + end) // 2
            
            days=self.get_day(weights,mid)
            if days <= D:
                end = mid
            else:
                start = mid + 1
             
              
        return end 
        
        
            
        


#
# @lc app=leetcode id=1011 lang=python3
#
# [1011] Capacity To Ship Packages Within D Days
#
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def timeConsumption(limit):
            days = totalWeight = 0
            for weight in weights:
                if totalWeight + weight > limit:
                    days += 1
                    totalWeight = weight
                else:
                    totalWeight += weight
            return days + 1
        left = max(weights)        
        right = sum(weights) + 1
        while left < right:
            mid = left + (right - left) // 2
            time = timeConsumption(mid)
            if time > D: left = mid + 1
            else: right = mid
        return left



class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left, right = max(weights), sum(weights)
        while left < right:
            mid, need, cur = (left + right) / 2, 1, 0
            for w in weights:
                if cur + w > mid:
                    need += 1
                    cur = 0
                cur += w
            if need > D: left = mid + 1
            else: right = mid
        return int(left)


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def condition(w) -> bool:
            curr,k = 0,0
            count = 0
            while k < len(weights):
                if curr + weights[k] > w:
                    count += 1
                    if count > D:
                        return False
                    curr = 0
                curr += weights[k]
                k += 1
            
            return count + 1 <= D
        
        left,right = max(weights),sum(weights)
        
        while left < right:
            mid = left + (right - left) // 2
            if condition(mid):
                right = mid
            else:
                left = mid + 1
            
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = sum(weights)
        while left<right:
            mid = left+(right-left)//2
            need=1
            cur=0
            for w in weights:
                if cur+w>mid:
                    need+=1
                    cur=0
                cur+=w
            if need>D:
                left=mid+1
            else:
                right=mid
        return left
    


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = int(sum(weights) / D)
        right = max(weights) * len(weights) / D
        
        def is_valid(weights, D, capacity):
            cur = capacity
            day = 0
            for w in weights:
                if cur + w <= capacity:
                    cur += w
                else:
                    cur = 0
                    if capacity < w:
                        return False
                    else:
                        cur = w
                        day += 1
            if day <= D:
                return True
            return False
        
        while left <= right:
            mid = left + (right - left) // 2
            if is_valid(weights, D, mid):
                right = mid - 1
            else:
                left = mid + 1
        return int(left)
            
                    


class Solution:
    def canShip(self, w, d, cap):
        i = 0
        res = 0
        while i < len(w):
            if w[i] > cap:
                return False
            remain = cap
            while i < len(w) and remain >= w[i]:
                remain -= w[i]
                i += 1
            res += 1
        return res <= d
                
                
                
                
    
    def shipWithinDays(self, w: List[int], D: int) -> int:
        if len(w) == 0:
            return 0
        start = max(w)
        end = sum(w)
        while start < end:
            mid = int((end - start) / 2) + start
            if self.canShip(w, D, mid):
                end = mid
            else:
                start = mid + 1
        
        return start
        
        
        
        
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def check_possible(capacity):
            count = 0
            i = 0
            while i < len(weights):
                count += 1
                if count > D or weights[i] > capacity:
                    return False
                curr_ship = 0
                while i < len(weights) and weights[i] + curr_ship <= capacity:
                    curr_ship += weights[i]
                    i += 1
            return True
        
        tot = 0
        largest = 0
        for w in weights:
            tot += w
            largest = max(largest, w)
            
        l = largest
        r = tot
        if check_possible(l):
            return l
        
        while l < r - 1:
            mid = (l + r) // 2
            if check_possible(mid):
                r = mid
            else:
                l = mid
                
        return r

class Solution:
    def get_day(self, weights, cap):
        i = 0
        res = 0
        wei = 0
        while i < len(weights): 
            if wei + weights[i] <= cap:
                    wei += weights[i]
                    i += 1
            else:
                wei = 0
                res += 1
        return res + 1
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        
        
                
        
        
        start, end = max(weights), sum(weights)
        
        while start < end:
            mid = (start + end) // 2
            
            days=self.get_day(weights,mid)
            if days <= D:
                end = mid
            else:
                start = mid + 1
             
              
        return end 
        
        
            
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def no_of_days(weights,W,D):
            count=1
            su=0
            i=0
            while i<len(weights):
                if su+weights[i]<=W:
                    su+=weights[i]
                    i+=1
                else:
                    su=weights[i]
                    i+=1
                    count+=1
            # print(count)
            return count
        
        
        def binary(weight,i,j,D):
            ans=0
            while i<=j:
                mid=int((i+j)/2)
                d=no_of_days(weight,mid,D)
                # print(\"d=\", d, i, \" \", j, \" \", mid)
                if d<=D:
                    ans=mid
                    j=mid-1
                else:
                    i=mid+1
                    
            return ans
        
        wi=max(weights)
        wj=wi*len(weights)
        a=binary(weights,wi,wj,D)
        
        return a
                
                
                
            
            


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l, r = max(weights), sum(weights)
        while l <= r:
            m = l + (r-l)//2
            if self.loadBalancer(weights, m) > D:
                l = m + 1
            elif self.loadBalancer(weights, m) <= D:
                r = m - 1
        return l
            
    def loadBalancer(self, weights, target):
        c, sum_ = 1, 0
        for i in weights:
            if sum_+i > target:
                c += 1
                sum_ = 0
            sum_ += i
        return c

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        lo = max(weights)
        hi = sum(weights)
        res = hi
        
        while lo <= hi:
            mid = lo + (hi-lo)//2
            
            # try packing 
            days = 0
            curr_weight = 0
            for i in range(len(weights)):
                if curr_weight + weights[i] > mid:
                    days += 1
                    curr_weight = weights[i]
                else:
                    curr_weight += weights[i]
            
            days += 1
            
            if days <= D:
                res = mid
                hi = mid - 1
            else:
                lo = mid + 1
        
        return res

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def possible(cap):
            d = D
            i = 0
            while i < len(weights) and weights[i] <= cap:
                cur = 0
                while i < len(weights) and cur + weights[i] <= cap:
                    cur += weights[i]
                    i += 1
                d -= 1
            
            if i < len(weights):
                return False
            return d >= 0
            
        total = sum(weights)
        
        l, r = 1, total
        ans = float('inf')
        
        while l <= r:
            m = l + (r-l)//2
            
            if possible(m):
                r = m - 1
                ans = min(ans, m)
            else:
                l = m + 1
        return ans

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def can(K):
            i = 0
            days = 0
            while i < len(weights) and days <= D + 1:
                k = K
                days += 1
                while i < len(weights) and k >= weights[i]:
                    k -= weights[i]
                    i += 1
            return days <= D
        
        l, r = 1, sum(weights)
        while l < r:
            mid = (l + r) // 2
            if can(mid):
                r = mid
            else:
                l = mid + 1
        return l
                    


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def can(K):
            i = 0
            days = 0
            while i < len(weights) and days <= D + 1:
                k = K
                days += 1
                while i < len(weights) and k >= weights[i]:
                    k -= weights[i]
                    i += 1
            return days <= D
        
        l, r = max(weights), sum(weights)
        while l < r:
            mid = (l + r) // 2
            if can(mid):
                r = mid
            else:
                l = mid + 1
        return l
                    


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def possible(cap):
            s = 0
            ship = 0
            i = 0
            while i<len(weights):
                s = s+weights[i]
                if s>cap:
                    ship=ship+1
                    s=0
                elif s<cap:
                    i = i+1
                else:
                    ship=ship+1
                    s=0
                    i=i+1
            if s==0:
                return ship<=D
            else:
                 return (ship+1)<=D
        lo = max(weights)
        hi = sum(weights)
        while lo<=hi:
            mid= lo+(hi-lo)//2
            if possible(mid):
                hi = mid-1
            else:
                lo = mid+1
        return lo

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = left * len(weights)//D

        def checkShipping(cap):
            # check whether we can ship all packages in D days
            days = 1
            onboard = 0
            for i, v in enumerate(weights):
                if onboard + v > cap:
                    days += 1
                    onboard = v
                else:
                    onboard += v

                if days > D:
                    return False
            return True

        ans = right
        while left <= right:
            mid = (right+left) // 2
            if checkShipping(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        SUM = sum(weights)
        MAX = max(weights)
        h = SUM
        l = max(MAX, SUM // D) - 1
        
        def canDo(arr, D, num):
            j = 0
            for i in range(D):
                # can ship a pool
                total = 0
                while j < len(arr) and total + arr[j] <= num:
                    total += arr[j]
                    j += 1
                if j == len(arr):
                    return True
                elif total == 0:
                    return False
            return j == len(arr)
        
        while h > l + 1:
            m = (l + h) // 2
            if canDo(weights, D, m):
                h = m
            else:
                l = m
        return l + 1

class Solution:
    def shipWithinDays(self, weights, D):
        left, right = max(weights), sum(weights)
        while left < right:
            mid, need, cur = (left + right) / 2, 1, 0
            for w in weights:
                if cur + w > mid:
                    need += 1
                    cur = 0
                cur += w
            if need > D: left = mid + 1
            else: right = mid
        return int(left)

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = 1
        right = max(weights) * len(weights)
        while left < right:
            mid = (left + right) // 2
            # print(left, mid, right)
            if self.possible(weights, D, mid):
                right = mid
            else:
                left = mid + 1
        return left
    
    def possible(self, weights, D, mid):
        cnt = 0
        tmp = 0
        for w in weights:
            if w > mid:
                return False
            if tmp + w > mid:
                tmp = w
                cnt += 1
            else:
                tmp += w
        if tmp != 0:
            cnt += 1
        return cnt <= D
            


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def ship_capacity(weights, D, capacity):
            days = 0
            sum_weights = 0
            for i in range(len(weights) - 1):
                sum_weights += weights[i]
                if sum_weights + weights[i + 1] > capacity:
                    days += 1
                    sum_weights = 0
            return days <= D - 1
        start = max(weights)
        end = sum(weights)
        while start <= end:
            mid = (start + end) // 2
            if ship_capacity(weights, D, mid):
                end = mid - 1
            else:
                start = mid + 1
        return start

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def checkIfCanShipWithinDDays(weights: List[int], D: int, capacity: int) -> bool:
            b, count, total = 0, 0, 0
            while b < len(weights):
                while total + weights[b] <= capacity:
                    total += weights[b]
                    b += 1
                    if b == len(weights):
                        count += 1
                        # double loop, should directly return
                        return count <= D
                count += 1
                total = 0
            return count <= D
        
        total = sum(weights)
        # attention: lb also bound by max element, or it can't fit in
        # so why not set lb directly to be the maximum element!
        lb = max(weights)
        ub = total
        while lb < ub:
            mid = lb + (ub - lb) // 2
            if checkIfCanShipWithinDDays(weights, D, mid):
                ub = mid
            else:
                lb = mid + 1
        return lb

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = sum(weights)
        while left + 1 < right:
            mid = left + (right-left)//2
            print(mid)
            curr = 0
            res = 1
            for w in weights:
                if curr + w > mid:
                    res += 1
                    curr = w
                else:
                    curr += w
            if res > D: #!!here use >, since mid is impossible to meet the requireent
                left = mid
            else: #!!here means <=, since there might be smaller mid 
                right = mid

        res = 1
        curr = 0
        for w in weights:
            if curr + w > left:
                res += 1
                curr = w
            else:
                curr += w
        if res <= D:
            return left
        return right

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        self.weight=weights
        self.D=D
        hi=sum(weights)
        lo=1        
        
        while hi!=lo: 
            mid=(hi+lo)//2
            if self.if_fit(mid):
                hi=mid
            else:
                lo=mid+1
                
        return hi
            
    def if_fit(self,cap):
        d=1
        count=0
        for val in self.weight: 
            if val>cap: 
                return False
            if val+count<=cap: 
                count+=val
            else: 
                count=val
                d+=1
                if d>self.D:
                    return False
        return True
                
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            


class Solution:
    def canFinish(self, weights, D, C):
        index = 0
        for _ in range(D):
            total = 0
            while index < len(weights) and total + weights[index] <= C:
                total += weights[index]
                index += 1
            if index == len(weights):
                return True
        return False
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l = 0 
        r = sum(weights)
        while l < r - 1:
            m = l + (r-l)//2
            if self.canFinish(weights, D, m):
                r = m
            else:
                l = m + 1
        
        if self.canFinish(weights, D, l):
            return l
        return r

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        total = sum(weights)
        # attention: lb also bound by max element, or it can't fit in
        #if total % D == 0:
        #    lb = total // D
        #else:
        #    lb = total // D + 1
        #lb = max(max(weights), lb)
        lb = max(weights)
        ub = total
        while lb < ub:
            mid = lb + (ub - lb) // 2
            if self.checkIfCanShipWithinDDays(weights, D, mid):
                ub = mid
            else:
                lb = mid + 1
        return lb
        
    def checkIfCanShipWithinDDays(self, weights: List[int], D: int, capacity: int) -> bool:
        b, count, total = 0, 0, 0
        while b < len(weights):
            while total + weights[b] <= capacity:
                total += weights[b]
                b += 1
                if b == len(weights):
                    count += 1
                    # double loop, should directly return
                    return count <= D
            count += 1
            total = 0
        return count <= D

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left, right = max(weights), max(weights)*len(weights)//D
        def checkShipping(capacity):
            days = 1
            total_weight = 0
            for weight in weights:
                if weight > capacity or days > D:
                    return False
                if weight + total_weight > capacity:
                    total_weight = weight
                    days +=1
                else:
                    total_weight += weight
            return days <= D  
        
        while left <= right:
            mid = left + (right-left) //2
            if checkShipping(mid):
                right = mid -1
            else:
                left = mid +1
        return left

class Solution:
    
    def can_ship(self, weights, D, max_weight):

        #print(weights, D)
        
        i = 0
        s = 0

        '''
        if len(weights)<D and max(weights)<=max_weight:
            return True
            
        if D==0 and len(weights)>0:
            return False

        if D==1 and sum(weights)<max_weight:
            return True

        while i<=len(weights)-1 and s<=max_weight:
            s+=weights[i]
            i+=1

        return self.can_ship(weights[i-1:], D-1, max_weight)
        '''

        while i<len(weights) and D>0:

            s = 0
            
            while i<len(weights) and s<=max_weight:
                s+=weights[i]
                
                if s>max_weight:
                    break

                i+=1

            D-=1

            #print(\"test \", i, D, weights)

        if D==0 and i<len(weights):
            return False

        return True

    def shipWithinDays(self, weights, D):

        left = min(weights)
        right = sum(weights)

        while left<right:

            mid = int((left+right)/2)
        
            if self.can_ship(weights, D, mid):
                right = mid
            else:
                left = mid

            #print(\"mid = \", mid, left, right)
            
            if right==left+1:
                if self.can_ship(weights, D, left):
                    return left
                else:
                    return right


        return mid


class Solution:
    def canShip(self, weights, capacity, D) -> bool:
        cnt, i = 0, 0
        cum = 0
        while i < len(weights):
            if cum + weights[i] <= capacity:
                cum += weights[i]
                i += 1
            else:
                cnt += 1
                cum = 0
        cnt += 1
        return cnt <= D
        
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l, r = max(weights), sum(weights)
        while l < r:
            mid = (l + r) // 2
            if self.canShip(weights, mid, D):
                r = mid
            else:
                l = mid + 1
        return r

def check(arr, mid, D):
    count = 1
    n = len(arr)
    cur_sum = 0
    for i in range(n):
        if cur_sum + arr[i] > mid:
            count += 1
            cur_sum = 0
        cur_sum += arr[i]
        if count > D:
            return False
    
    return count <= D


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        max_weight = sum(weights)
        min_weight = max(weights)
        ans = float('inf')
        
        while min_weight <= max_weight:
            mid = int((max_weight + min_weight)/2)
            if check(weights, mid, D) == True:
                ans = min(ans, mid)
                max_weight = mid - 1
            else:
                min_weight = mid + 1
        
        return ans


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def test(capacity):
            count = 0
            current_sum = 0
            i = 0
            
            while i < len(weights) and count < D:
                while i < len(weights) and current_sum + weights[i] <= capacity:
                    current_sum += weights[i]
                    i += 1
                
                count += 1
                current_sum = 0
            
            return count <= D and i == len(weights)
        
        
        l, r = 1, sum(weights)
        
        while l < r:
            mid = (l + r) // 2
            
            if test(mid):
                r = mid
            else:
                l = mid + 1
        
        return l

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l, r = max(weights), sum(weights)
        while l < r:
            mid = (l+r)//2
            d = self.check(weights, mid)
            if d > D:
                l, r = mid+1, r
            else:
                l, r = l, mid
        return l
            
            
    def check(self, weights, size):
        c = 0
        i = 0
        days = 0
        while True:
            if i == len(weights):
                break

            while i < len(weights) and c + weights[i] <= size:
                c += weights[i]
                i += 1
            c = 0
            days += 1
        return days

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        maxCap = sum(weights) # 8
        minCap = max(weights) # 3
        ans = maxCap

        # binary search
        lo = minCap
        hi = maxCap

        while lo <= hi:
            mi = lo + (hi - lo) // 2 # mid = left + (right - left) // 2
            # test if cap works
            daysLeft = D
            dailyCap = mi
            i = 0
            while i < len(weights) and daysLeft:
                wei = weights[i]
                if wei > dailyCap:
                    daysLeft -= 1
                    dailyCap = mi
                elif wei == dailyCap:
                    daysLeft -= 1
                    dailyCap = mi
                    i += 1
                else:
                    dailyCap -= wei
                    i += 1
            if i == len(weights):
                ans = min(ans, mi)
                hi = mi - 1
            else:
                lo = mi + 1
        return ans


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def condition(k):
            ind, load, days = 0, 0, 0
            while ind < len(weights):
                #print(ind, load, days)
                if weights[ind] + load <= k:
                    load += weights[ind]
                    ind += 1
                else:
                    load = 0
                    days += 1
            return days + 1 <= D
        
        #print(condition(15))
        
        
        left, right = max(weights), sum(weights)
        while left < right:
            mid = left + (right - left) // 2
            if condition(mid):
                right = mid
            else:
                left = mid + 1
        
        return left
    
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        maxCap = sum(weights)
        minCap = max(weights)
        ans = maxCap
        lo = minCap
        hi = maxCap
        while lo <= hi:
            mi = lo + (hi - lo) // 2
            daysLeft = D
            dailyCap = mi
            i = 0
            while i < len(weights) and daysLeft:
                wei = weights[i]
                if wei > dailyCap:
                    daysLeft -= 1
                    dailyCap = mi
                elif wei == dailyCap:
                    daysLeft -= 1
                    dailyCap = mi
                    i += 1
                else:
                    dailyCap -= wei
                    i += 1
            if i == len(weights):
                ans = min(ans, mi)
                hi = mi - 1
            else:
                lo = mi + 1
        return ans


class Solution:
    def shipWithinDays(self, arr: List[int], D: int) -> int:
        def count(arr, x):
            res = i = 0
            while i < len(arr):
                z = 0
                while i < len(arr) and z + arr[i] <= x:
                    z += arr[i]
                    i += 1
                res += 1
            return res
        
        end = start = 0
        for i in arr:
            end += i
            start = max(start, i)
        while start <= end:
            mid = start + (end - start)//2
            if count(arr, mid) > D:
                start = mid + 1
            else:
                out = mid
                end = mid - 1
        return out

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        s = max(weights)
        e = max(weights) * len(weights) // D
        
        def dayCount(weights, cap, D):
            day = 1
            total = 0
            for i in range(len(weights)):
                if total + weights[i] <= cap:
                    total += weights[i]
                else:
                    day += 1
                    total = weights[i]
            return day <= D
            
        while s <= e:
            mid = (s+e) // 2
            if dayCount(weights, mid, D):
                e = mid - 1
            else:
                s = mid + 1
        return s

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        # do a binary search
        # return has to do with weights
        # so initialize right = sum(weights)
        # a ship that can carry everything
        
        left = max(weights)
        right = 999999999999999999 # this ship over-carries for sure
        
        while left < right:
            # keep track of days
            # if we ship all packages and days too little, it means
            # we can afford to decrease our ship-capacity
            # which means right=mid
            
            # else if days too much,
            # we must increase our ship-capacity
            # so left = mid
            
            # mid is our current ship capacity
            

            mid = (left+right) // 2
            
            days_needed = 1
            cargo = 0
            
            for w in weights:
                if cargo + w > mid:
                    # cannot fit this next package to current cargo
                    days_needed += 1
                    cargo = w
                else:
                    # can fit
                    cargo += w

            
            if days_needed > D:
                # this means it must be greater than mid, for sure
                left = mid + 1
            else:
                right = mid
                
            
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l = 0
        r = sum(weights)
        best = r
        while l <= r:
            mid = l + (r - l) // 2
            if self.works(mid, weights, D):
                best = mid
                r = mid - 1
            else:
                l = mid + 1
                
        return best
    
    def works(self, cap, weights, d):
        if cap < max(weights):
            return False
        idx = 0
        total_days = 0
        while idx < len(weights):
            cur_cap = 0
            while cur_cap < cap and idx < len(weights):
                if cur_cap + weights[idx] > cap:
                    break
                cur_cap += weights[idx]
                idx += 1
            
            total_days += 1
        
        return total_days <= d


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        cap_min = max(weights)
        cap_max = sum(weights)

        # binary search the minimum cap

        while cap_min < cap_max:
            cap_mid = (cap_min + cap_max) // 2

            days = self._cal_num_of_days(weights, cap_mid)

            if days > D:
                cap_min = cap_mid + 1
            elif days < D:
                cap_max = cap_mid
            elif days == D:
                cap_max = cap_mid

        return cap_min

    def _cal_num_of_days(self, weights: List[int], cap: int) -> int:
        days = 0
        i = 0

        while i < len(weights):
            current_load = 0
            while i < len(weights) and current_load + weights[i] <= cap:
                current_load += weights[i]
                i += 1
            days += 1
        return days


class Solution:
    def check (self,weights: List[int], D: int, cap: int) -> bool:
        
        load = 1
        total = 0
        for i in range (len(weights)):
            total += weights[i]
            
            if (i!= len(weights)-1):
                if ((total + weights[i+1])>cap):
                    total= 0 
                    load+=1
                    if (load>D):
                        return False 
                
        if (load <= D):
            return True
        
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        lo = max(weights) 
        hi = sum(weights)
        
        while (lo< hi):
            mid= lo + ((hi-lo)//2)
            
            if (self.check(weights,D,mid)):
                hi = mid 
            
            else: 
                lo = mid +1 
                
        return lo 


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        '''
        weights = [1,2,3,4,5,6,7,8,9,10], D = 5
        
        left = 10
        right = 15
        mid = 15
        '''
        left = max(weights)
        right = sum(weights)
        while left < right:
            mid = left + (right - left) // 2
            count = 1
            bucket = 0
            for w in weights:
                if bucket + w <= mid:
                    bucket += w
                else:
                    bucket = w
                    count += 1
            if count <= D:
                right = mid
            else:
                left = mid + 1
        return left
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def test(x): 
            times, i = 0, 0
            while i < len(weights):
                times += 1
                cur = 0
                #print('   ', weights[i:])
                while i < len(weights) and cur+weights[i] <= x: 
                    cur += weights[i]
                    i += 1
            
            return times
        
        l, r = max(weights), sum(weights)
        while l <= r:
            mid = (l+r)//2
            #print(mid, l, r)
            days = test(mid)
            if days <= D: r = mid - 1
            else: l = mid + 1
            #print('   it takes', days, 'days to ship with limit', mid)
        
        if days > D: mid += 1
        return mid
        
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def days_taken(capacity, arr):
            days = 0
            i = 0
            while i < len(arr):
                j = i
                bucket = capacity
                days += 1
                while j < len(arr) and arr[j] <= bucket and bucket > 0:
                    bucket -= arr[j]
                    j += 1
                i = j
            return days
        
        low = max(weights)
        high = sum(weights)
        
        
        
        while low < high:
            mid = (low + high) // 2
            days_by_mid = days_taken(mid, weights)
            
            if days_by_mid <= D:
                high = mid
            else:
                low = mid + 1
        
        return low
        
        
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        start, end = max(weights), sum(weights) + 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if self._can_ship(weights, mid, D):
                end = mid
            else:
                start = mid
        return start if self._can_ship(weights, start, D) else end
    
    def _can_ship(self, weights, capacity, D):
        days_needed = 0
        i = 0
        while i < len(weights):
            curr_w = 0
            while i < len(weights) and curr_w + weights[i] <= capacity:
                curr_w += weights[i]
                i += 1
            days_needed += 1
        return days_needed <= D

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        if D == 1:
            return sum(weights)
        start = max(max(weights),-(-sum(weights)//D))
        end = sum(weights)
        n = len(weights)
        def validate(x):
            count = 0
            i = 0
            while count < D:
                cur = 0
                while i< n and cur <= x:
                    cur += weights[i]
                    i += 1
                i-=1
                count += 1
            if i == n-1 and cur <= x:
                return True
            return False

        while start < end:
            m = (start+end)//2
            if validate(m):
                end = m
            else:
                start = m+1
        return start
            
            


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def feasible(w):
            i = 0 
            for day in range(D):
                ship_w = 0
                while i < len(weights):
                    #print(str(w - ship_w)+\">=\"+str(weights[i]))
                    if w - ship_w >= weights[i]:
                        ship_w += weights[i]
                    else:
                        break
                    i+=1
            return i == len(weights)
        left, right = max(weights), sum(weights)
        while left < right:
            mid = (left+right) >> 1
            if feasible(mid):
                right = mid 
            else:
                left = mid + 1
        return left


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:

        def check_capacity(capacity) -> bool:
            days = 1
            ship_weight = 0
            for weight in weights:
                ship_weight += weight
                if ship_weight > capacity:
                    ship_weight = weight
                    days += 1
                    if days > D:
                        return False
            return True

        left = max(weights)
        right = left * len(weights) // D
        while left < right:
            mid = left + (right - left) // 2
            if check_capacity( mid ):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        memo = {}
        high = sum(weights)
        low = ceil(high / D)
        best = low
        mid = low + (high - low) // 2
        memo[mid] = is_possible(weights, mid, D)
        memo[mid + 1] = is_possible(weights, mid + 1, D)
        
        while memo[mid] or not memo[mid + 1]:
            if high == low and high == best:
                
                return best
            
            # print(low)
            # print(high)
            # print(mid)
            # print(\"----\")
            if not memo[mid]: #not mid and not mid + 1, answer is higher
                low = mid + 1
                
            else: # mid and mid + 1, answer is lower
                high = mid
                
            mid = low + (high - low) // 2
            if mid not in memo:
                memo[mid] = is_possible(weights, mid, D)
                
            if mid + 1 not in memo:
                memo[mid + 1] = is_possible(weights, mid + 1, D)
            
        return mid + 1
    
def is_possible(weights, max_w, D):
    total = 0
    
    for i, weight in enumerate(weights):
        if weight > max_w:
            return False
        
        if total + weight > max_w:
            total = 0
            D -= 1
            
            # full before the last one is added
            if D == 0:
                return False
        
        total += weight
        
            
    return True

class Solution:
    def possible(self, capacity):
        ret = 0
        cur = 0
        for w in self.weights:
            if w > capacity:
                return False
            if cur + w <= capacity:
                cur += w
            else:
                ret += 1
                cur = w
        if w > 0:
            ret += 1
        return ret <= self.D
        
        
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        self.weights = weights
        self.D = D
        
        # print(self.possible(15))
        lo, hi = 1, 0x3f3f3f3f
        while lo <= hi:
            mid = lo + ((hi-lo) >> 1)

            if self.possible(mid):
                hi = mid - 1
            else:
                lo = mid + 1
        if self.possible(lo):
            return lo
        return lo + 1
                
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        memo = {}
        high = sum(weights)
        low = ceil(high / D)
        best = low
        mid = low + (high - low) // 2
        memo[mid] = is_possible(weights, mid, D)
        memo[mid + 1] = is_possible(weights, mid + 1, D)
        
        while memo[mid] or not memo[mid + 1]:
            if high == low and high == best:
                # print(\"###\")
                # print(memo[2])
                # print(memo[3])
                return best
            
            # print(low)
            # print(high)
            # print(mid)
            # print(\"----\")
            if not memo[mid]: #not mid and not mid + 1, answer is higher
                low = mid
                
            else: # mid and mid + 1, answer is lower
                high = mid
                
            mid = low + (high - low) // 2
            if mid not in memo:
                memo[mid] = is_possible(weights, mid, D)
                
            if mid + 1 not in memo:
                memo[mid + 1] = is_possible(weights, mid + 1, D)
            
        return mid + 1
    
def is_possible(weights, max_w, D):
    total = 0
    
    for i, weight in enumerate(weights):
        if weight > max_w:
            return False
        
        if total + weight > max_w:
            total = 0
            D -= 1
            
            # full before the last one is added
            if D == 0:
                return False
        
        total += weight
        
            
    return True

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        l, r = max(weights), sum(weights)
        
        while l<=r:
            
            mid = l + (r-l)//2
            
            need, cur = 1, 0
            
            for w in weights:
                
                if cur+w > mid:
                    need += 1
                    cur = 0
                    
                cur += w
                
            if need > D:
                l = mid + 1
            else:
                r = mid-1
                
        return l

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l = max(weights)
        r = sum(weights)

        def canFitInD(m):
            n = 1
            current = 0
            for i in range(len(weights)):
                if current + weights[i] <= m:
                    current += weights[i]
                else:
                    n += 1
                    current = weights[i]
                    if n > D:
                        return False
            return True

        while l < r:
            mid = l + (r - l)//2
            if canFitInD(mid):
                r = mid
            else:
                l = mid+1

        return l
# leetcode submit region end(Prohibit modification and deletion)


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:

            n = len(weights)
            if not n: return n
            
            total = sum(weights)
            target = total//D
            left, right = max(weights), total
            
            def check(s,total, D):
                cur = 0
                i=0
                while i<len(weights):
                    w = weights[i]
                    if cur+w>s:
                        total-=cur
                        D-=1
                        cur=0
                    else:
                        cur+=w
                        i+=1
                    
                    if D==1:
                        if total>s: return False
                        else: return True
                return True
            
            ans = total
            while left<=right:
                mid = (left+right+1)//2
                if check(mid,total,D): 
                    ans = min(ans,mid)
                    right = mid-1
                else: 
                    left = mid+1
            
            return ans

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def check(capacity, D):
            d = 0
            i = 0
            c = capacity
            while(d < D):
                if(i == len(weights)):
                    return True
                if(weights[i] <= c):
                    if(weights[i] > capacity):
                        return False
                    c -= weights[i]
                    i+=1
                else:
                    c = capacity
                    d += 1
            return False
        l=0; r=max(weights)*len(weights)
        while(l<r):
            mid = l + (r-l)//2
            if(check(mid, D)):
                r = mid
            else:
                l = mid+1
        return l

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def isOK(weights,D,w):
            count=1
            weight=0
            for i in range(0,len(weights)):
                if weights[i]>w or count>D:
                    return False
                if weight+weights[i]>w:
                    count+=1
                    weight=0
                weight+=weights[i]
            if count<=D:
                return True
            else:
                return False
            
        left=max(weights)
        right=sum(weights)
        while left<=right:
            middle=(left+right)//2
            if isOK(weights,D,middle)==True:
                right=middle-1
            else:
                left=middle+1
        return left
            
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def good(cap):
            i, tmp, ans = 0, 0, 1
            while i < len(a):
                if tmp + a[i] <= cap:
                    tmp += a[i]
                else:
                    ans += 1
                    tmp = a[i]
                i += 1
            return ans <= D
        
        a = weights
        lo, hi = max(a), sum(a)
        while lo < hi:
            mid = (lo + hi) // 2
            if good(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def helper(w):
            i=0
            cnt=0
            while cnt<D:
                curr=0
                while i<len(weights):
                    if curr+weights[i]<=w:
                        curr+=weights[i]
                        i+=1
                    else:
                        break
                cnt+=1
            return False if i!=len(weights) else True
        l,r=max(weights),sum(weights)
        while l<=r:
            mid=(l+r)//2
            if helper(mid):
                r=mid-1
            else:
                l=mid+1
        return l
        
            
            


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        low, high = max(weights), sum(weights)
            
        while low<high:
            mid = low + (high-low)//2
            d = 1
            curr_sum = 0
            for idx in range(len(weights)):
                if curr_sum + weights[idx] >mid:
                    d += 1
                    curr_sum =0
                curr_sum += weights[idx]
            
            if d <=D:
                high = mid
            else:
                low = mid+1
        return low
            


from typing import List
import bisect
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l = min(weights)
        r = max(weights) * len(weights)
        
        def isOk(capacity):
            item = 0
            day = 0
            while item < len(weights):
                s = 0
                while True:
                    if weights[item] > capacity:
                        return False
                    if s + weights[item]> capacity:
                        break
                    else:
                        s = s + weights[item]
                        item += 1
                    if item >= len(weights):
                        break
                day += 1
            return day <= D
        print((isOk(15)))
        while r - l > 1:
            mid = l + (r - l)//2
            if isOk(mid):
                r = mid
            else:
                l = mid
        return r
print((Solution().shipWithinDays([1,2,3,4,5,6,7,8,9,10],5)))



def isOK(cap, weights, D):
    cnt = 1
    total = 0
    for i in range(len(weights)):
        if total + weights[i] > cap:
            cnt += 1
            total = weights[i]
        else:
            total += weights[i]
    return cnt <= D

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left, right = max(weights), max(weights) * len(weights) // D
        
        
        while left <= right:
            mid = (right+left) //2
            if isOK(mid, weights, D):
                right = mid -1
            else:
                left = mid +1
        return left 


from typing import List
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l = -1
        r = max(weights) * len(weights)
        
        def isOk(capacity):
            item = 0
            day = 0
            while item < len(weights):
                s = 0
                while True:
                    if weights[item] > capacity:
                        return False
                    if s + weights[item]> capacity:
                        break
                    else:
                        s = s + weights[item]
                        item += 1
                    if item >= len(weights):
                        break
                day += 1
            return day <= D


        while r - l > 1:
            mid = l + (r - l)//2
            if isOk(mid):
                r = mid
            else:
                l = mid
                
        return r



class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        mini = max(weights)
        maxi = sum(weights)
        
        if len(weights) == 1:
            return weights[0]
        
        while maxi >= mini:
            mid = (maxi + mini) // 2 
            if self.check(weights, mid) < D:
                maxi = mid - 1
            elif self.check(weights, mid) > D:
                mini = mid + 1
            else:
                maxi = mid - 1
            print(mini)
        return mini
            
    def check(self, piles, num):
        res = 0
        i = 0
        count = 0
        while i < len(piles):
            if res + piles[i] < num:
                res += piles[i]
            elif res+piles[i] == num:
                res = 0
                count += 1
            else:
                res = piles[i]
                count += 1
            i += 1
        count = count if res == 0 else count + 1
        return count

class Solution:
    def possibleWithinDays(self, weights, D, capacity):
        x = 0
        i = 1
        total = 0
        while(i <= D):
            current_sum = 0
            #print(i)
            
            while(x < len(weights) and current_sum + weights[x] <= capacity):
                current_sum += weights[x]
                total += weights[x]
                x += 1
            #print(\"x: \",x)
            #print(\"cur_sum: \",current_sum)
            #print(\"total: \",total)
            i += 1
        
        if total >= sum(weights):
                return True
        #print(\"i\",i,\"x\",x)
        return False
            
    
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        total_sum = sum(weights)
        left = 0
        right = total_sum
        
        while(left < right):
            middle = (left+right)//2
            aux = self.possibleWithinDays(weights,D,middle)
            if aux:
                right = middle
            else:
                left = middle+1
        
        return left
        
    #1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...50000 
    #1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 55
    #that capacity makes True if we can do it in less or equal than D
   
    #1+55 = 56/2 = 28


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        sums = [0] * (len(weights) + 1)
        for i in range(len(weights)):
            sums[i + 1] = weights[i] + sums[i]
        
        def backtracking(i, cap, d):
            if i == len(sums):
                return True
            if sums[-1] - sums[i - 1] > cap * d:
                return False
            j = i
            while j < len(sums):
                if sums[j] - sums[i - 1] > cap:
                    break
                j += 1
            return backtracking(j, cap, d - 1)
        
        l, h = max(weights), sum(weights)
        
        while l <= h:
            m = (l + h) // 2
            if backtracking(1, m, D):
                h = m - 1
            else:
                l = m + 1
        return l

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        n=len(weights)
        l=max(weights)
        r=n*max(weights)
        pre=[weights[0]]
        for i in range(1,len(weights)):
            pre.append(pre[-1]+weights[i])
        def checker(val) -> bool:
            x=0
            y=0
            j=0
            i=0
            while(i<len(pre)):
                x=pre[i]-y
                if(x==val):
                    x=0
                    y=pre[i]
                    j+=1
                    if(j>D):
                        return False
                elif(x>val):
                    x=0
                    y=pre[i-1]
                    i-=1
                    j+=1
                    if(j>D):
                        return False
                i+=1
            if(j==D)and(x!=0):
                return False
            return True
        while(l<r):
            mid=(l+r)//2
            if(checker(mid)==True):
                r=mid
            else:
                l=mid+1
        return l
        
            


from typing import List
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l = -1
        r = max(weights) * len(weights)
        
        def isOk(capacity):
            item = 0
            day = 0
            while item < len(weights):
                s = 0
                while True:
                    if weights[item] > capacity:
                        return False
                    if s + weights[item]> capacity:
                        break
                    else:
                        s = s + weights[item]
                        item += 1
                    if item >= len(weights):
                        break
                day += 1
            return day <= D
        print((isOk(100000)))


        while r - l > 1:
            mid = l + (r - l)//2
            if isOk(mid):
                r = mid
            else:
                l = mid
                
        return r



class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        end = sum(weights)
        start = end // D
        
        while start < end:
            mid = (start + end) // 2
            # print(start, end, mid)
            
            days = 1
            curr_sum = 0
            for i in range(len(weights)):
                if weights[i] > mid:
                    days = D + 1
                    break
                if curr_sum + weights[i] > mid:
                    days += 1
                    if days > D:
                        break
                    curr_sum = weights[i]
                else:
                    curr_sum += weights[i]
            # print(days)
            
            if start == mid:
                if days > D:
                    return end
                else:
                    return start
                
            if days > D:
                start = mid
            else:
                end = mid
        return start

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        preSum = [0]
        for weight in weights:
            preSum.append(weight + preSum[-1])
        N = len(weights)
        
        def shipWeights(ship):
            D0 = D
            start = 0
            l = 1
            r = N
            while D0 > 0 and l <= N:
                if ship >= preSum[r]-preSum[start]:
                    l = r+1
                while r > l:
                    m = (l + r) // 2
                    if preSum[m]-preSum[start] > ship:
                        r = m
                    else:
                        l = m + 1
                D0 -= 1
                start = l - 1
                r = N

            if l == N+1:
                return True
            return False
        
        wl = max(weights)
        wr = sum(weights)
        
        if D >= len(weights):
            return wl
        if D == 1:
            return wr
        while wr > wl:
            wm = (wr + wl) // 2
            if shipWeights(wm):
                wr = wm
            else:
                wl = wm + 1
        return wl

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        self.weights = weights
        self.days = days
        left, right = max(weights), sum(weights)
        while left < right: 
            mid = left + (right - left) // 2
            if self.isFit(mid):
                right = mid
            else: 
                left = mid+1
        return left
            
        
    def isFit(self, capacity):
        weight_index = 0
        for day in range(0, self.days):
            current_capacity = capacity
            while current_capacity >= 0:
                if weight_index == len(self.weights):
                    return True
                weight = self.weights[weight_index]
                if (current_capacity - weight < 0):
                    break
                else:
                    current_capacity -= weight
                    weight_index += 1
        return False
             
                
                
            
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        start, end = max(weights), sum(weights)
        while start+1 < end:
            mid = (start + end) // 2
            days = self.get_days(weights, mid)
            if days > D:
                start = mid + 1
            elif days <= D:
                end = mid
        if self.get_days(weights, start) <= D:
            return start
        else:
            return end
    
    def get_days(self, weights, cap):
        tot = 0
        res = 1
        i = 0
        while i < len(weights):
            tot += weights[i]
            if tot > cap:
                res += 1
                tot = 0
            else:
                i += 1
        return res
    


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        # Return true if all packages can be shipped within D days
        # with capacity capacity.
        # Note that if I can ship with capacity, I can definitely ship with
        # any value > capacity
        def check(capacity):
            cur = ix = 0
            day = 1
            while ix < len(weights):
                if cur + weights[ix] == capacity:
                    cur = 0
                    day += 1
                elif cur + weights[ix] > capacity:
                    cur = weights[ix]
                    day += 1
                else:
                    cur += weights[ix]
                ix += 1
            return ix == len(weights) and day <= D
        
        left, right = max(weights), sum(weights)
        while left < right:
            mid = left + (right - left) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def is_possible(C):
            if C < max(weights):
                return False
            
            d, i, cap, n = 1, -1, 0, len(weights)
            while d <= D:
                while i < n - 1 and cap + weights[i + 1] <= C:
                    cap += weights[i + 1]
                    i += 1
                d += 1
                cap = 0
            if i < n - 1: return False
            return True
        
        left, right = 0, sum(weights)
        while left < right:
            mp = left + (right - left) // 2
            if is_possible(mp):
                right = mp
            else:
                left = mp + 1
                
        return left


class Solution:
    def canBeFerried(self, weights: List[int], D: int, capacity: int) -> bool:
        i, j, days = 0, 0, 0
        while i < len(weights):
            sum_ = 0
            j = 0
            while (sum_ <= capacity):
                if (i + j < len(weights)):
                    sum_ += weights[i + j]
                else:
                    days += 1
                    return days <= D
                j += 1
            # print(f\"After exiting second loop: sum_ = {sum_}, j = {j}\")
            days += 1
            # print(f\"Increased days to {days}\")
            
            if i == len(weights) - 1:
                break
            i += j - 1
            # print(f\"Set i = {i}\")
            if days > D:
                return False
        return days <= D
            
    
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        low = max(weights)
        high = len(weights) * low
        
        while low < high:
            mid = (low + high) // 2
            if self.canBeFerried(weights, D, mid):
                high = mid
            else:
                low = mid + 1
        return low


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def canDo(k):
            d = 1
            curr = 0
            for w in weights:
                if w > k:
                    return False
                curr += w
                if curr > k:
                    d +=1
                    curr = w
            return d <= D
        
        l,r = 0,10**18
        while l < r:
            m = (l+r)//2
            # print(l,r,m,canDo(m))
            if canDo(m):
                r = m
            else:
                l = m+1
        return l
                
                


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        l,h = max(weights),sum(weights)
        
        
        while l < h:
            
            
            days = 1
            
            total_weight = 0
            
            capacity = (l+h)//2
            # print(capacity)
            
            for weight in weights:
                total_weight += weight
                
                if total_weight > capacity:
                    # print(total_weight)
                    days += 1
                    total_weight = weight
            if days <= D:
                h = capacity
            else:
                l = capacity+1
        return l
                    
            # print(days,total_weight)
            # break
                    
                


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        l = max(weights)
        r = sum(weights)
        
        def calc(cap):
            cnt = 0
            cur = 0
            for w in weights:
                cur += w
                if cur > cap:
                    cur = w
                    cnt += 1
            return cnt + 1 <= D
        
        while l < r:
            mid = (l + r) // 2
            good = calc(mid)
            if good:
                r = mid
            else:
                l = mid + 1
        return l

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left, right = max(weights), sum(weights)
        while left < right:
            mid = left + (right-left) // 2
            if self.__countDays(weights, mid) <= D:
                right = mid
            else:
                left = mid+1
        return left
        
    def __countDays(self, weights, capacity):
        days = 0
        cur_w = 0
        for w in weights:
            cur_w += w
            if cur_w > capacity:
                days += 1
                cur_w = w
        return days + 1

import sys
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = left * len(weights) // D
        while left < right: 
            mid = left + (right - left) // 2
            c = 0 # capacity
            d = 1 # days
            for w in weights:
                if c + w <= mid:
                    c += w
                else:
                    d += 1
                    c = w
            if d > D:
                left = mid + 1
            else:
                right = mid
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def check(W: int) -> bool:
            count, total = 1, 0
            for w in weights:
                total += w
                if total > W:
                    count += 1
                    total = w
                    if count > D: return False
            
            return True
        
        left, right = max(weights), sum(weights)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if check(mid):
                right = mid
            else:
                left = mid + 1
        
        return left
        
                
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def feasible(capacity):
            day = 1
            total = 0
            
            for weight in weights:
                total += weight
                if total > capacity:
                    total = weight
                    day += 1
                    
                    if day > D:
                        return False
                
            
            return True
        
        low, high = max(weights), sum(weights)
        
        while low < high:
            mid = low + (high-low)//2
            
            if feasible(mid):
                high = mid
            
            else:
                low = mid+1
            
        return low

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def feasible(capacity):
            days = 1
            total = 0
            
            for wt in weights:
                total += wt
                if total > capacity:
                    total = wt
                    days += 1
                    if days > D:
                        return False

            return True

        left = max(weights)
        right = sum(weights)
        
        while left < right:
            mid = left + (right - left)//2
            if feasible(mid):
                right = mid
            else:
                left = mid+1
        
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def binarySearch(capacity):
            days = 1
            total = 0
            for i in weights:
                total+=i
                if total > capacity:#wait for the next day
                    total = i
                    days+=1
                    if days > D:#cannot ship
                        return False
            return True
        left,right = max(weights),sum(weights)
        while left < right:
            mid = left+(right-left)//2
            if binarySearch(mid):
                right = mid
            else:
                left = mid+1
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def isPossible(capacity):
            day=1
            w=0
            for wt in weights:
                w+=wt
                if w>capacity:
                    day+=1
                    w=wt
            return day
        
        start,end=max(max(weights),sum(weights)//D),sum(weights)
        
        while start<end:
            mid=start+(end-start)//2
            days=isPossible(mid)
            if days<=D:
                end=mid
            elif days>D:
                start=mid+1
            
        return start
                


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def feasible(capacity):
            
            days = 1
            total = 0
            for weight in weights:
                total += weight
                
                if total > capacity:
                    total = weight
                    days += 1
                    if days > D:
                        return False
            return True
        
        left = max(weights)
        right = sum(weights)
        
        while left < right:
            mid = left + (right - left)//2
            
            if feasible(mid):
                right = mid
            else:
                left = mid+1
                
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        
        n = len(weights)
        
        hi = 0
        lo = 0
        for w in weights:
            lo = max(lo, w)
            hi += w
        
        if D == 1:
            return hi
        
        while lo < hi:
            mid = lo + ((hi - lo)//2)
            cur, days = 0, 1
            for w in weights:
                cur += w
                if cur > mid:
                    days += 1
                    cur = w
            if days > D:
                lo = mid + 1
            else:
                hi = mid
            # print(lo, mid, hi)
        return lo

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l, r = max(weights), sum(weights)

        while l < r:
            mid = (r - l) // 2 + l
            day = self.weightWhetherWork(weights, mid)
            if day > D:
                l = mid + 1
            else:
                r = mid
        return l

    def weightWhetherWork(self, weights, mid):
        temp = mid
        day = 1
        for i in weights:
            if temp >= i:
                temp -= i
            else: 
                temp = mid
                temp -= i
                day += 1
        return day

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        low = max(weights)
        high = sum(weights)
        total =0
        parts=1
        while(low<high):
            total=0
            parts=1
            mid = int((low+high)/2)
            for w in weights:
                if total+w<=mid:
                    total=total+w
                else:
                    total=w
                    parts+=1
            if parts>D:
                low=mid+1
            else:
                high=mid
        return low

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        lo,hi = max(weights),sum(weights)
        
        while lo < hi:
            mid = (lo + hi)//2
            tot,res = 0,1
            for a in weights:
                if a+tot>mid:
                    tot = a
                    res+=1
                else:
                    tot+=a
            if res <= D:
                hi = mid
            else :
                lo = mid + 1
        return lo

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def calDays(weights, cap):
            days = 1
            acc_w = 0
            for w in weights:
                acc_w += w
                if acc_w > cap:
                    days += 1
                    acc_w = w
            return days
            
        lo = max(weights)
        hi = lo * len(weights) // D
        while lo < hi:
            med = lo + (hi-lo)//2
            days = calDays(weights, med)
            if days <= D:
                hi = med
            else:
                lo = med+1
        return hi


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = sum(weights)
        while  left < right:
            mid, load, need = (left + right)//2, 0, 1
            for w in weights:
                load += w
                if load > mid:
                    need += 1
                    load = w
            if need > D: left = mid + 1
            else: right = mid
        return left        
                
                


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = sum(weights)
        
        while(left < right):
            mid = int((left+right)/2)
            print(mid)
            curr_weight = 0
            days = 1
            for w in weights:
                if(curr_weight+w <= mid):
                    curr_weight+= w
                else:
                    curr_weight = w
                    days += 1
            if(days > D):
                left = mid+1
            else:
                right = mid
        
        return left
                    


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:

        def canship(cap):
            d = 1
            s = 0
            for w in weights:
                if s+w<=cap:
                    s+=w
                else:
                    d+=1
                    s=w
                if d>D:
                    return False
            return True


        M = max(weights)
        if D==len(weights):
            return M
        
        lo, hi = M-1, sum(weights)
        
        while hi-lo>1:
            h = (hi+lo)//2
            if canship(h):
                hi=h
            else:
                lo=h
        
        return hi

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l, r = max(weights), sum(weights)
        
        def isPossible(capacity):
            days = 0
            temp = 0
            for w in weights:
                if temp + w <= capacity:
                    temp += w
                else:
                    days += 1
                    temp = w
            return days + 1 <= D
        
        while l < r:
            mid = l + (r - l) // 2
            if isPossible(mid):
                r = mid
            else:
                l = mid + 1
        
        return l

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def possible(K):
            if K < max(weights):
                return False
            day = 1 
            temp = K 
            for we in weights:
                if temp < we:
                    temp = K-we
                    day +=1
                else:
                    temp -= we
                
            return not (day>D)
        lo, hi = max(weights), sum(weights)
        
        while lo<hi:

            mi = (lo+hi)//2
            if not possible(mi):
                lo = mi+1
            else:
                hi = mi

        return lo


class Solution:
    def shipWithinDays(self, weights: List[int], limit: int) -> int:
        
        def count_days(cap: int) -> int:
            cur_weight = 0
            days = 1

            for w in weights:
                if cur_weight + w > cap:
                    days += 1
                    cur_weight = w
                else:
                    cur_weight += w
                # print(f\"cap= {cap}, weight={w}, cur_weight={cur_weight}, days={days}\")

            return days

        left = max(weights)
        right = sum(weights)

        while left < right:
            mid = left + (right - left) // 2
            time = count_days(mid)
            # print(f\"cap={mid}, left={left}, right={right}, time={time}\")
            if time > limit:
                left = mid + 1
            else:
                right = mid

        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l, r = max(weights), sum(weights)
        
        def checkCapacity(maxCap):
            day = 1
            temp = 0
            for i in weights:
                temp+=i
                if temp>maxCap:
                    temp = i
                    day+=1
                if day>D:
                    return False
            return True
            
        
        while l<r:
            mid = l+(r-l)//2
            if checkCapacity(mid):
                r=mid
            else:
                l=mid+1
                
        return l

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        left = max(weights)
        right = sum(weights)
        
        while left < right:
            mid = left + (right-left)//2
            
            if self.isFeasible(mid, weights, D):
                right = mid
            else:
                left = mid + 1
            
        return left
    def isFeasible(self, capacity, weights, D):
        
        total = 0
        days = 1
        for weight in weights:
            if total + weight <= capacity:
                
                total += weight
            else:
                total = weight
                days += 1
                if days > D:
                    return False
        return True
            


from collections import deque
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def canShip(capacity):
            nonlocal D
            count, loaded = 1, 0
            for w in weights:
                if loaded + w <= capacity:
                    loaded += w
                else:
                    count += 1
                    loaded = w
            return count <= D
    
        max_weight = max(weights)
        low, high = sum(weights) // D,  max_weight * len(weights) // D + 1
        while low < high:
            mid = low + (high - low) // 2
            if mid < max_weight or not canShip(mid):
                low = mid + 1
            else:
                high = mid
        return low


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left, right = max(weights), sum(weights)
        while left < right:
            mid, need, cur = (left + right) // 2, 1, 0
            for w in weights:
                if cur + w > mid:
                    need += 1
                    cur = 0
                cur += w
            if need > D:
                left = mid + 1
            else: right = mid
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left, right = max(weights), sum(weights)
        while left < right:
            mid, need, cur = (left + right) // 2, 1, 0
            for w in weights:
                if cur + w > mid:
                    need += 1
                    cur = 0
                cur += w
            if need > D:
                left = mid + 1
            else:
                right = mid

        return left


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = sum(weights)
        while left < right:
            mid = (left + right)//2
            current = 0
            need = 1
            for w in weights:
                if current + w > mid:
                    need += 1
                    current = 0
                current += w
                
            if need > D:
                left = mid + 1
            else:
                right = mid
        return left


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = sum(weights)
        
        res = right
        while left <= right:
            mid = left + (right - left)//2
            d = self.get_day(weights, mid)
            #print(left, right, mid, d)
            if d <= D:
                res = min(res, mid)
                right = mid - 1
            else:
                left = mid + 1
        return res

    
    def get_day(self, weights, cap):
        cur = 0
        res = 0
        for x in weights:
            if cur + x > cap:
                res += 1
                cur = 0
            cur += x

        return res + 1


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def numberofDaysWithCapacity(weights,mid):
            sum,c=0,1
            for i in range(len(weights)):
                sum+=weights[i]
                if(sum>mid):
                    c+=1
                    sum=weights[i]
            return c
        left,right=max(weights),sum(weights)
        while(left<=right):
            mid=left+(right-left)//2
            daysRequired=numberofDaysWithCapacity(weights,mid)
            if daysRequired>D:
                left=mid+1
            else:
                res=mid
                right=mid-1
        return res


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
       
        def fun(t):
            s= 0
            d= 0
            for i in range(n):
                s=s+weights[i]
                if s>t:    
                    d=d+1
                    s = weights[i]
            return d
        
        n = len(weights)        
        lo, hi = max(weights),sum(weights)
        while(lo <= hi):
            c= lo + (hi - lo)//2
            if fun( c )< D:
                hi=c-1
            else:
                lo=c+1
        return lo        

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:

        def days_required( t ):
            running_sum = 0
            days = 0
            for i in range(n):
                running_sum += weights[i]
                if running_sum > t:    
                    days += 1
                    running_sum = weights[i]
            return days
        
        n = len(weights)        
        lo, hi = max(weights), sum(weights)
        while(lo <= hi):
            capacity = lo + (hi - lo)//2
            if days_required( capacity ) < D:
                hi = capacity - 1
            else:
                lo = capacity + 1
        return lo                       

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        high = 0
        low = 0
        for weight in weights:
            high += weight
            low = max(low, weight)
        
        # Search over the possible solutions of [max value, sum of weights]
        while (low < high):
            mid = (high + low) // 2
            
            days = 1
            cur_weight = 0
            for weight in weights:
                if cur_weight + weight > mid:
                    cur_weight = 0
                    days += 1
                cur_weight += weight
                    
            # Did it in too many days, need higher capacity
            if days > D:
                low = mid + 1
            # Did it in too few days, need lower capacity
            else:
                high = mid

                
        return low
                


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def canShip(capacity: int) -> bool:
            nonlocal D
            count = 1
            curcap = 0 
            for w in weights:
                if curcap + w <= capacity:
                    curcap += w
                else:
                    count += 1
                    curcap = w
            return count <= D
            
        
        max_weight = max(weights)
        lo = sum(weights) // D
        hi = max_weight * (len(weights)) // D + 1
        while lo < hi:
            mid = (lo + hi) // 2
            if mid < max_weight or not canShip(mid):
                lo = mid + 1
            else:
                hi = mid
        return lo
                


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        mi = max(weights)
        ma = sum(weights)
        
        def canFit(cap):
            num = 1
            re = cap 
            for i in range(len(weights)):
                x = weights[i]
                if x > re:
                    re = cap 
                    num += 1
                re -= x
            return num <= D
        
        while mi < ma:
            mid = mi + (ma - mi) // 2
            if canFit(mid):
                ma = mid
            else:
                mi = mid+1
        return mi

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def check(cap):
            cnt, load = 0, 0
            for x in weights:
                # cap is too small to load even one package
                if x > cap: return False
                if load + x < cap:
                    load += x
                elif load + x == cap:
                    cnt, load = cnt+1, 0
                else:
                    cnt, load = cnt+1, x
            return cnt + (load > 0) <= D
        
        l, r = 1, sum(weights)
        while l < r:
            p = l + (r - l) // 2
            if not check(p): l = p+1
            else: r = p
        return l

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        high = sum(weights)
        low = max(weights)
        
        def check(cap):
            cnt = 1
            summ = 0
            for w in weights:
                if summ+w <= cap:
                    summ += w
                else:
                    cnt += 1
                    summ = w
                if cnt > D:
                    return False
            return True
        
        while low!=high:
            mid = (low+high)//2
            if check(mid):
                high = mid
            else:
                low = mid+1
        
        return low


class Solution:
    # def shipWithinDays(self, weights: List[int], D: int) -> int:
    #     if D == 1:
    #         return sum(weights)
    #     curCap = sum(weights)//D
    #     days = 1
    #     i = 0
    #     cap = curCap
    #     while i < len(weights):
    #         cap -= weights[i]
    #         if cap <= 0:
    #             days += 1
    #             if cap == 0:
    #                 i += 1
    #             cap = curCap
    #         else:
    #             i += 1
    #         if days > D:
    #             curCap += 1
    #             days = 1
    #             i = 0
    #             cap = curCap
    #     return curCap
    
    def shipWithinDays(self, weights, D):
        l, r = max(weights), sum(weights)
                            
        while l < r:
            m, days, curWeight = (l + r) // 2, 1, 0
            for weight in weights:
                if curWeight + weight > m:
                    days += 1
                    curWeight = 0
                if days > D:
                    l = m + 1
                    break
                curWeight += weight
            else: 
                r = m
        return l
    
        # def shipWithinDays(self, weights, D):
    #     left, right = max(weights), sum(weights)
    #     while left < right:
    #         mid, need, cur = (left + right) // 2, 1, 0
    #         for w in weights:
    #             if cur + w > mid:
    #                 need += 1
    #                 cur = 0
    #             cur += w
    #         if need > D: left = mid + 1
    #         else: right = mid
    #     return left


from collections import defaultdict
class Solution:
     def canShipWithinDays(self, weights: List[int], D: int, maxWeight: int) -> bool:
        if max(weights) > maxWeight:
            return False
        
        lswt = 0
        nD = 1
        for w in weights:
            if lswt + w <= maxWeight:
                lswt += w
            else:
                nD += 1
                lswt = w
        return nD <= D
    
     def shipWithinDays(self, weights: List[int], D: int) -> int:
        maxweight = sum(weights)
        minweight = max(weights)
        while maxweight > minweight + 1:
            mw = (maxweight + minweight) // 2 
            if self.canShipWithinDays(weights, D, mw):
                maxweight = mw
            else:
                minweight = mw
        
        if self.canShipWithinDays(weights, D, minweight):
            return minweight
        else:
            return maxweight

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def canShip(capacity: int) -> bool:
            nonlocal D
            count = 1
            curcap = 0 
            for w in weights:
                if curcap + w <= capacity:
                    curcap += w
                else:
                    count += 1
                    curcap = w
            return count <= D
            
        
        max_weight = max(weights)
        lo = sum(weights) // D
        hi = max_weight * len(weights) // D + 1
        while lo < hi:
            mid = (lo + hi) // 2
            if mid < max_weight or not canShip(mid):
                lo = mid + 1
            else:
                hi = mid
        return lo
                


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def can(x):
            res, sum = 1, 0
            for w in weights:
                if w > x: return False
                if sum + w > x:
                    res += 1
                    sum = w
                else: sum += w
            return res <= D
        mx, sum = 0, 0
        for i in weights: 
            mx, sum = max(mx, i), sum + i
        lo, hi = mx, sum
        while lo < hi:
            mi = (hi - lo) // 2 + lo
            if not can(mi): lo = mi + 1
            else: hi = mi
        return lo

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def condition(minWeight):
            dayCt = 1
            curWeight = 0
            for i, w in enumerate(weights):
                if curWeight + w <= minWeight:
                    curWeight += w
                else:
                    dayCt += 1
                    curWeight = w
            
            return dayCt <= D
        
        l = max(weights)
        r = sum(weights)
        
        while l < r:
            m = l + (r - l) // 2
            if condition(m):
                r = m
            else:
                l = m + 1
        
        return l


# from itertools import combinations 
# import sys
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
#         if D == 1:
#             return sum(weights)
        
#         all_comb = combinations(range(1,len(weights)), D-1)
        
#         res = sys.maxsize
#         for comb in all_comb:
#             cap = 0
#             # print(comb)
#             for i in range(len(comb) + 1):
#                 if i == 0:
#                     cap = max(cap, sum(weights[:comb[i]]))
#                 elif i == len(comb):
#                     cap = max(cap, sum(weights[comb[i-1]:]))
#                 else:
#                     cap = max(cap, sum(weights[comb[i-1]:comb[i]]))
#             res = min(res, cap)
#         return(res)

        lower = max(weights)
        upper = sum(weights)
        
        while abs(lower - upper) > 1:
            mid = (lower + upper) // 2
            # print(lower, upper)
            if self.is_shipped(mid, weights, D):
                upper = mid
            else:
                lower = mid
        
        if lower == upper or self.is_shipped(lower, weights, D):
            return lower
        else:
            return upper
                
    def is_shipped(self, cap, weights, D):
        tmp = 0
        count = 1
        for i in range(len(weights)):
            tmp += weights[i]
            if tmp == cap:
                count += 1
                tmp = 0
            elif (tmp > cap):
                count += 1
                tmp = weights[i]
        return count <= D

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def feasible(capacity):
            days = 1
            total = 0
            for i in range(len(weights)):
                total += weights[i]
                if total > capacity:
                    days += 1
                    total = weights[i]
                if days > D:
                    return False
            return True
    
        left, right = max(weights), sum(weights)
        while left < right:
            mid = left + (right - left)//2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = sum(weights)
        retval = sum(weights)
        while left<=right:
            mid = left + (right-left)//2
            temp,count = 0,1
            for i in range(len(weights)):
                temp+=weights[i]
                if temp>mid:
                    temp = weights[i]
                    count+=1
                elif temp==mid:
                    temp = 0
                    count+=1
            if count>D:
                left = mid+1
            else:
                retval = mid
                right = mid-1
        return retval


class Solution:
    def isValidCapacity(self, weights, D, capacity):
        totalDays = 1
        i = 0
        runningSum = 0

        for i in range(len(weights)):
            if runningSum + weights[i] > capacity:
                runningSum = weights[i]
                totalDays += 1
            else:
                runningSum += weights[i]

        return totalDays <= D
    
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        low = max(weights)
        high = sum(weights)

        while low < high:
            mid = (low + high) // 2

            if self.isValidCapacity(weights, D, mid):
                high = mid
            else:
                low = mid + 1

        return low
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def can_ship(x):
            cnt = 1
            curr = 0
            for w in weights:
                if w > x:
                    return False
                
                if curr + w > x:
                    curr = w
                    cnt += 1
                else:
                    curr += w
                    
                if cnt > D:
                    return False
                
            return cnt <= D
        
        
        left, right = 1, sum(weights)
        while left < right:
            mid = (right - left) // 2 + left
            
            if can_ship(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = sum(weights)
        while left < right:
            mid = left + (right - left) // 2
            if self.condition(mid, weights) <= D:
                right = mid
            else:
                left = mid+1
        return left
    
    def condition(self, k, weights):
        d = 0
        cur_weight = 0
        for weight in weights:
            if cur_weight + weight == k:
                d += 1
                cur_weight = 0
            elif cur_weight + weight > k:
                d += 1
                cur_weight = weight
            else:
                cur_weight += weight
        return d+1 if cur_weight > 0 else d

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        total = sum(weights)
        maxW = max(weights)
        low = total//D
        high = low + maxW
        
        def isok(weights, D, cap):
            curr = cap
            count = 1
            for w in weights:
                if w > cap:
                    return False
                if curr - w < 0:
                    count += 1
                    curr = cap - w
                else:
                    curr -= w
            return count <= D
        
        while low != high:
            mid = (low + high)//2
            if isok(weights, D, mid):
                high = mid
            else:
                low = mid+1
        return low

class Solution:
    def numD(self,arr,n):
        count=0
        ans=0
        for i in range(len(arr)):
            count+=arr[i]
            if count>n:
                ans+=1
                count=arr[i]
        return ans+1
    
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l=-1
        r=25000000
        for i in range(len(weights)):
            if weights[i]>l:
                l=weights[i]
            #r+=weights[i]
        
        while l<=r:
            mid = (l+r)//2
            if self.numD(weights,mid)<=D:
                r=mid-1
            elif self.numD(weights,mid)>D:
                l=mid+1
            
        return l


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        # do a binary search
        # return has to do with weights
        # so initialize right = sum(weights)
        # a ship that can carry everything
        
        left = max(weights)
        right = sum(weights) # this ship over-carries for sure
        
        while left < right:
            # keep track of days
            # if we ship all packages and days too little, it means
            # we can afford to decrease our ship-capacity
            # which means right=mid
            
            # else if days too much,
            # we must increase our ship-capacity
            # so left = mid
            
            # mid is our current ship capacity
            

            mid = (left+right) // 2
            
            days_needed = 1
            cargo = 0
            
            for w in weights:
                if cargo + w > mid:
                    # cannot fit this next package to current cargo
                    days_needed += 1
                    cargo = w
                else:
                    # can fit
                    cargo += w

            
            if days_needed > D:
                # this means it must be greater than mid, for sure
                left = mid + 1
            else:
                right = mid
                
            
        return left

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l = max(weights)
        r = sum(weights)
        length = len(weights)
        while l <= r:
            mid = l + (r-l)//2
            cur = 0
            toD = 1
            
            for i in range(length):
                if cur + weights[i] > mid:
                    toD +=1
                    cur= 0
                cur+=weights[i]
            if toD > D:
                l = mid + 1
            else:
                r = mid-1
        return l


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = sum(weights)
        while left < right:
            mid = left + (right - left) // 2
            if self.condition(mid, weights) <= D:
                right = mid
            else:
                left = mid+1
        return left
    
    def condition(self, k, weights):
        d = 0
        cur_weight = 0
        for weight in weights:
            if cur_weight + weight == k:
                d += 1
                cur_weight = 0
            elif cur_weight + weight > k:
                d += 1
                cur_weight = weight
            else:
                cur_weight += weight
        return d+1 if cur_weight > 0 else d
        '''def count_days(k, w):
            curr_wt = 0
            count = 0
            for x in weights:
                if curr_wt+x > k:
                    count = count+1
                    cur_wt = x
                elif curr_wt+x==k:
                    count=count+1
                    curr_wt = 0
                else:
                    curr_wt = curr_wt+x
            if curr_wt > 0: return count+1
            else: return count
                
        
        l = max(weights)
        r = sum(weights)
        while l<r:
            mid = l+((r-l)//2)
            if count_days(mid, weights) <= D:
                r = mid
            else:
                l = mid+1
        return l'''
        


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        lo = max(weights)
        hi = sum(weights)
        n = len(weights)
        
        while lo<hi:
            guess = lo+(hi-lo)//2
            
            guessDays = 1
            currLoad = 0
            for i in range(n):
                if currLoad + weights[i]>guess:
                    currLoad = 0
                    guessDays+=1
                
                currLoad+=weights[i]
            
            if guessDays<=D:
                hi = guess
            else:
                lo = guess+1
                
                
        
        return lo
                    
                    


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def __can(capacity):
            days = 0
            partial_sum = 0
            for i in range(len(weights)):
                if partial_sum + weights[i] > capacity:
                    partial_sum = 0
                    days += 1
                
                partial_sum += weights[i]
            
            days += 1
                
            return days <= D
        
        
        lo, hi = max(weights), sum(weights)
        
        while lo + 1 < hi:
            
            mid = (lo + hi) // 2
            
            if __can(mid) == True:
                hi = mid
            else:
                lo = mid
        
        return lo if __can(lo) == True else hi


from collections import defaultdict
class Solution:
     def canShipWithinDays(self, weights: List[int], D: int, maxWeight: int) -> bool:
        if max(weights) > maxWeight:
            return False
        
        lswt = 0
        nD = 1
        for w in weights:
            if lswt + w <= maxWeight:
                lswt += w
            else:
                nD += 1
                lswt = w
        return nD <= D
    
     def shipWithinDays(self, weights: List[int], D: int) -> int:
        # maxweight = sum(weights)
        minweight = max(weights)
        maxweight = minweight * len(weights) / D
        while maxweight > minweight + 1:
            mw = (maxweight + minweight) // 2 
            if self.canShipWithinDays(weights, D, mw):
                maxweight = mw
            else:
                minweight = mw
        
        if self.canShipWithinDays(weights, D, minweight):
            return int(minweight)
        else:
            return int(maxweight)

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l, h = max(weights), sum(weights)
        total = h
        
        while l <= h:
            m = (l + h) // 2
            days, count, t = D, 0, 0
            for w in weights:
                if days == 0:
                    break
                if count + w > m:
                    count = w
                    days -= 1
                else:
                    count += w
                t += w
            
            if t == total and days > 0:
                h = m - 1
            else:
                l = m + 1
        return l

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
      l, r = max(weights), sum(weights)
      
      while l + 1 < r:
        mid = (l + r) // 2
        
        if self.calculateNumberOfDays(weights, mid) > D:
          l = mid
        else:
          r = mid
      if self.calculateNumberOfDays(weights, l) <= D:
        return l
      else:
        return r
    
    def calculateNumberOfDays(self, weights, K):
      num_of_days = 0
      _sum = 0
      for i in range(len(weights)):
        if _sum + weights[i] > K:
          num_of_days += 1
          _sum = weights[i]
        else:
          _sum += weights[i]
      if _sum:
        num_of_days += 1
      return num_of_days
    
    
    
    # // 3,2,2,4,1,4
    # l = 1, r = 16, m = 8 -> 1 + 1 + 1 = 3


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
    
    # search space
    # MIN (LEFT) has to be at least the largest weight of the packages, otherwise boat cannot carry it
    # MAX (RIGHT) is the sum of all packages, since boat can carry all of it in ONE day
        left = 0
        right = 0
        for i in range(len(weights)):
            left = max(weights[i], left)
            right += weights[i]

        while left < right:
            mid = (left+right)//2

            if self.greedy_match(mid, weights, D):
                right = mid
            else:
                left = mid + 1

        return left
    
    
    
    
    
    
    
    
    
    
    
    def greedy_match(self, boat_weight, weights, days):
        cur_days = 1
        cur_weight = 0
        for i in range(len(weights)):
            if cur_weight + weights[i] > boat_weight:
                cur_weight = 0
                cur_days += 1
                if cur_days > days:
                    return False
            cur_weight += weights[i]
        return True


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        weights_sum = sum(weights)
        
        def necessary_days(capacity):
            days = 0
            ws = 0
            for w in weights:
                if ws + w <= capacity:
                    ws += w
                else:
                    days += 1
                    ws = w
                    
            return days + 1
        
        low = max(weights)
        high = weights_sum
        capacity_guess = (low + high) // 2
        
        while low <= high:
            d = necessary_days(capacity_guess)
            
            if d <= D:
                high = capacity_guess - 1
            else:
                low = capacity_guess + 1
                
            capacity_guess = (low + high) // 2
            
        return low


class Solution:
    def check(self, weights, limit):
        cur = 0
        count = 1
        for i in range(len(weights)):
            if cur + weights[i] > limit:
                count += 1
                cur = weights[i]
            else:
                cur += weights[i]
        
        return count
    
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l = max(weights)
        r = sum(weights)
        ans = 1
        
        while l <= r:
            mid =  int((r + l) / 2)
            if self.check(weights, mid) <= D:
                ans = mid
                r = mid - 1
            else:
                l = mid + 1
        return ans

class Solution:
    def check(self, weights, limit):
        cur = 0
        count = 1
        for i in range(len(weights)):
            if cur + weights[i] > limit:
                count += 1
                cur = weights[i]
            else:
                cur += weights[i]
        
        return count
    
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l = max(weights)
        r = sum(weights)
        ans = 1
        
        while l <= r:
            mid = l + int((r - l) / 2)
            if self.check(weights, mid) <= D:
                ans = mid
                r = mid - 1
            else:
                l = mid + 1
        return ans

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        left = max(weights)
        right = sum(weights)
        while left < right:
            mid = left + (right - left) // 2
            buckets = 1
            count = 0
            for w in weights:
                if count + w <= mid:
                    count += w
                else:
                    buckets += 1
                    count = w
            if buckets > D:
                left = mid + 1
            else:
                right = mid
        return left