Given an array arr[] of N weights. Find the least weight capacity of a boat to ship all weights within D days.
The i^{th} weight has a weight of arr[i]. Each day, we load the boat with weights given by arr[i].We may not load more weight than the maximum weight capacity of the ship.
Note: You have to load weights on the boat in the given order.
 
Example 1:
Input:
N = 3
arr[] = {1, 2, 1}
D = 2
Output:
3
Explanation:
We can ship the weights in 2 days
in the following way:-
Day 1- 1,2
Day 2- 1
Example 2:
Input:
N = 3
arr[] = {9, 8, 10}
D = 3
Output:
10
Explanation:
We can ship the weights in 3 days
in the following way:-
Day 1- 9
Day 2- 8
Day 3- 10
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function leastWeightCapacity() which takes 2 integers N, and D, and an array arr of size N as input and returns the least weight capacity of the boat required.
Expected Time Complexity: O(N*log(Sum of weights - max(list of weights))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ D ≤ N ≤ 10^{5}
1 ≤ arr[i] ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def leastWeightCapacity(self, arr, N, D):

        # code here 

Solutions:
class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def possible(arr, c, D):
			daysreq = 1
			curload = 0
			for weight in arr:
				curload += weight
				if curload > c:
					daysreq += 1
					curload = weight
			return daysreq <= D
		total = 0
		maxload = 0
		for weight in arr:
			total += weight
			maxload = max(maxload, weight)
		l = maxload
		r = total
		while l < r:
			mid = (l + r) // 2
			if possible(arr, mid, D):
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def leastWeightCapacity(self, weights, N, days):

		def CalculateCapacity(capacity):
			count = 1
			max = capacity
			for weight in weights:
				if weight > max:
					max = capacity
					count += 1
				max -= weight
			return True if count <= days else False
		(start, end) = (max(weights), sum(weights))
		while start < end:
			mid = start + (end - start) // 2
			if CalculateCapacity(mid):
				end = mid
			else:
				start = mid + 1
		return start


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		(left, right) = (max(arr), sum(arr))
		while left < right:
			mid = (left + right) // 2
			(current_load, required_days) = (0, 1)
			for weight in arr:
				if current_load + weight > mid:
					required_days += 1
					current_load = 0
				current_load += weight
			if required_days <= D:
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		left = max(arr)
		right = sum(arr)
		ans = 0
		while left <= right:
			mid = (left + right) // 2
			days = 0
			i = 0
			remainder = mid
			days = 0
			while i < N:
				days += 1
				remainder -= arr[i]
				i += 1
				while i < N and remainder >= arr[i]:
					remainder -= arr[i]
					i += 1
				remainder = mid
			if days <= D:
				ans = mid
				right = mid - 1
			else:
				left = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def cap(capacity):
			days_req = 1
			curr_load = 0
			for weights in arr:
				curr_load += weights
				if curr_load > capacity:
					days_req += 1
					curr_load = weights
				else:
					continue
			return days_req <= D
		low = max(arr)
		high = sum(arr)
		while low < high:
			mid = low + (high - low) // 2
			if cap(mid):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		l = max(arr)
		r = sum(arr)
		while l <= r:
			mid = (l + r) // 2
			days = 1
			count = 0
			for i in range(len(arr)):
				count += arr[i]
				if count > mid:
					days += 1
					count = arr[i]
			if days > D:
				l = mid + 1
			else:
				r = mid - 1
		return l


class Solution:

	def numdays(self, arr, cap, maxval):
		if maxval > cap:
			return float('inf')
		curr = 0
		days = 1
		for ele in arr:
			if curr + ele <= cap:
				curr += ele
			else:
				days += 1
				curr = ele
		return days

	def leastWeightCapacity(self, arr, N, D):
		maxval = max(arr)
		(low, high) = (1, sum(arr))
		mind = float('inf')
		while low <= high:
			mid = (low + high) // 2
			daysreq = self.numdays(arr, mid, maxval)
			if daysreq <= D:
				mind = mid
				high = mid - 1
			else:
				low = mid + 1
		return mind


class Solution:

	def leastWeightCapacity(self, weights, n, days):
		low = max(weights)
		high = sum(weights)
		while low < high:
			mid = low + high >> 1
			sumation = 0
			daysTaken = 1
			for weight in weights:
				sumation += weight
				if sumation > mid:
					sumation = weight
					daysTaken += 1
			if daysTaken > days:
				low = mid + 1
			else:
				high = mid
		return high


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		weights = arr
		days = D
		lo = 1
		hi = sum(weights)
		ans = 0

		def canship(mid):
			day = 0
			temp = 0
			for i in range(len(weights)):
				if weights[i] > mid:
					return False
				if temp + weights[i] <= mid:
					temp = temp + weights[i]
				else:
					day += 1
					temp = weights[i]
			day += 1
			if day <= days:
				return True
			return False
		while lo <= hi:
			mid = (lo + hi) // 2
			if canship(mid):
				ans = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, d):
		low = max(arr)
		high = sum(arr)
		ans = high
		while low <= high:
			mid = (low + high) // 2
			day = 1
			s = 0
			for i in arr:
				if s + i <= mid:
					s += i
				else:
					day += 1
					s = i
			if day == d:
				ans = min(ans, mid)
				high = mid - 1
			elif day > d:
				low = mid + 1
			elif day < d:
				ans = mid
				high = mid - 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def Capacity(days):
			cur_sum = 0
			cur_days = 1
			for n in arr:
				cur_sum += n
				if cur_sum > days:
					cur_days += 1
					cur_sum = n
					if cur_days > D:
						return False
			return True
		low = max(arr)
		high = sum(arr)
		while low < high:
			mid = (low + high) // 2
			if Capacity(mid):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def leastWeightCapacity(self, w, N, d):

		def check(w, c):
			a = 0
			d = 0
			for i in w:
				if a + i > c:
					d += 1
					a = 0
				a += i
			return d + 1
		l = max(w)
		r = sum(w)
		res = 0
		while l <= r:
			mid = (l + r) // 2
			if check(w, mid) > d:
				l = mid + 1
			else:
				res = mid
				r = mid - 1
		return res


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		(low, high) = (max(arr), sum(arr))

		def possible(c):
			(days, load) = (1, 0)
			for i in arr:
				load += i
				if load > c:
					days += 1
					load = i
			return days
		while low < high:
			mid = (low + high) // 2
			days = possible(mid)
			if days <= D:
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def ship_weight(sw):
			days = 1
			packages = 0
			for w in arr:
				if w > sw:
					return 0
				if packages + w > sw:
					days += 1
					packages = w
					if days > D:
						return 0
				else:
					packages += w
			return 1
		low = min(arr)
		high = sum(arr)
		res = -1
		while low <= high:
			mid = (low + high) // 2
			if ship_weight(mid):
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def approve(val):
			count = 1
			cur = 0
			for p in arr:
				cur += p
				if cur > val:
					cur = p
					count += 1
			return count
		l = max(arr)
		r = sum(arr)
		res = l
		while l <= r:
			mid = l + (r - l) // 2
			if approve(mid) <= D:
				res = mid
				r = mid - 1
			else:
				l = mid + 1
		return res


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		if N == D:
			return max(arr)
		else:
			(left, right) = (max(arr), sum(arr))
			while left < right:
				mid = (left + right) // 2
				(curr_sum, days_needed) = (0, 1)
				for i in arr:
					if curr_sum + i > mid:
						days_needed += 1
						curr_sum = i
					else:
						curr_sum += i
				if days_needed > D:
					left = mid + 1
				else:
					right = mid
			return left


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		left = max(arr)
		right = sum(arr)
		while left < right:
			need = 1
			curr = 0
			mid = (right + left) // 2
			for w in arr:
				if w + curr > mid:
					curr = 0
					need += 1
				curr += w
			if need > D:
				left = mid + 1
			else:
				right = mid
		return right


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		low = max(arr)
		high = sum(arr)
		while low <= high:
			mid = (low + high) // 2
			st = 1
			summ = 0
			for i in arr:
				summ += i
				if summ > mid:
					st += 1
					summ = i
			if st <= D:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def ispos(self, arr, mid, D):
		da = 1
		s = 0
		for i in range(len(arr)):
			s += arr[i]
			if s > mid:
				da += 1
				s = arr[i]
		return da <= D

	def leastWeightCapacity(self, arr, N, D):
		mx = max(arr)
		su = sum(arr)
		if N == D:
			return mx
		lo = mx
		hi = su
		ans = 0
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			if self.ispos(arr, mid, D) == True:
				ans = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		low = max(arr)
		high = sum(arr)
		while low < high:
			mid = (low + high) // 2
			count = 1
			summa = 0
			for item in arr:
				summa += item
				if summa > mid:
					count += 1
					summa = item
			if count > D:
				low = mid + 1
			else:
				high = mid
		return high


class Solution:

	def check(self, arr, mid, k):
		cow = 1
		pos = 0
		for i in arr:
			if i + pos <= mid:
				pos += i
			else:
				cow += 1
				if cow > k or i > mid:
					return False
				pos = i
		return True

	def slve(self, arr, s, e, k, ans):
		if s > e:
			return ans
		mid = (s + e) // 2
		if self.check(arr, mid, k) == True:
			ans = mid
			return self.slve(arr, s, mid - 1, k, ans)
		else:
			return self.slve(arr, mid + 1, e, k, ans)

	def leastWeightCapacity(self, arr, N, D):
		j = sum(arr)
		res = self.slve(arr, 0, j, D, -1)
		return res


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		l = max(arr)
		r = sum(arr)
		while l <= r:
			mid = (l + r) // 2
			ans = 1
			w = 0
			for i in arr:
				w += i
				if w > mid:
					ans += 1
					w = i
			if ans <= D:
				r = mid - 1
			else:
				l = mid + 1
		return l


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		ans = sum(arr)
		low = 1
		high = ans
		while low <= high:
			mid = (low + high) // 2
			total = 0
			count = 0
			for i in range(len(arr)):
				val = arr[i]
				if val > mid:
					count += 100000.0
					break
				if total + val <= mid:
					total += val
					if i == 0:
						count = 1
					continue
				count += 1
				total = val
			if count <= D:
				ans = min(ans, mid)
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		(i, j) = (1, sum(arr))

		def checksum(arr, k, d):
			m = max(arr)
			if m > k:
				return False
			c = 1
			s1 = 0
			for i in arr:
				if s1 + i > k:
					c = c + 1
					s1 = i
					if c > d:
						return False
					continue
				s1 = s1 + i
			return True
		ans = -1
		while j >= i:
			mid = (i + j) // 2
			y = checksum(arr, mid, D)
			if y:
				ans = mid
				j = mid - 1
			if y == False:
				i = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def check(capacity):
			(total, count) = (0, 1)
			for num in arr:
				total += num
				if total > capacity:
					count += 1
					total = num
			return count
		(l, r) = (max(arr), sum(arr))
		while l <= r:
			mid = l + r >> 1
			days_taken = check(mid)
			if days_taken > D:
				l = mid + 1
			else:
				r = mid - 1
		return l


import sys

class Solution:

	def leastWeightCapacity(self, arr, N, D):
		s = max(arr)
		if N == D:
			return s
		e = sum(arr)
		ans = sys.maxsize
		while s <= e:
			m = (s + e) // 2
			days = 1
			oneDayLoad = 0
			for i in range(N):
				oneDayLoad += arr[i]
				if oneDayLoad > m:
					days += 1
					oneDayLoad = arr[i]
			if days <= D:
				ans = min(ans, m)
				e = m - 1
			else:
				s = m + 1
		return ans


class Solution:

	def check(self, arr, w, D):
		curr = 0
		d = 1
		for i in range(len(arr)):
			if curr + arr[i] <= w:
				curr += arr[i]
			else:
				d += 1
				curr = arr[i]
				if d > D:
					return False
		return True

	def leastWeightCapacity(self, arr, N, D):
		mn = sorted(arr)[-1]
		mx = sum(arr)
		while mn < mx:
			mid = (mn + mx) // 2
			if self.check(arr, mid, D):
				mx = mid
			else:
				mn = mid + 1
		return mn


class Solution:

	def check(self, N, D, arr, mid):
		st = 0
		cow = 1
		for i in arr:
			if st + i <= mid:
				st += i
			else:
				cow += 1
				if cow > D or i > mid:
					return False
				st = i
		return True

	def leastWeightCapacity(self, arr, N, D):
		s = 0
		e = sum(arr)
		mid = s + (e - s) // 2
		ans = -1
		while s <= e:
			if self.check(N, D, arr, mid) == True:
				ans = mid
				e = mid - 1
			else:
				s = mid + 1
			mid = s + (e - s) // 2
		return ans


class Solution:

	def minDayCheck(self, midWeight, arr, n):
		reqDays = 1
		remCap = midWeight
		for i in range(n):
			if arr[i] <= remCap:
				remCap -= arr[i]
			else:
				reqDays += 1
				remCap = midWeight
				remCap -= arr[i]
		return reqDays

	def leastWeightCapacity(self, arr, N, D):
		(totalWeights, maxWeight) = (0, -1)
		for i in range(N):
			totalWeights += arr[i]
			maxWeight = max(arr[i], maxWeight)
		s = maxWeight
		e = totalWeights
		selectedWeight = totalWeights
		while s <= e:
			m = s + (e - s) // 2
			d = self.minDayCheck(m, arr, N)
			if d > D:
				s = m + 1
			else:
				selectedWeight = min(selectedWeight, m)
				e = m - 1
		return selectedWeight


class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def iswithintime(arr, capacity, D):
			days = 1
			currentload = 0
			for i in arr:
				currentload += i
				if currentload > capacity:
					days += 1
					currentload = i
			return days <= D
		total = 0
		maxload = 0
		for i in arr:
			total += i
			maxload = max(maxload, i)
		low = maxload
		high = total
		while low < high:
			mid = (low + high) // 2
			if iswithintime(arr, mid, D):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		(l, r) = (max(arr), sum(arr))
		res = r

		def capShip(cap):
			(ships, curCap) = (1, cap)
			for w in arr:
				if curCap - w < 0:
					curCap = cap
					ships += 1
				curCap -= w
			return ships <= D
		while l <= r:
			cap = (l + r) // 2
			if capShip(cap):
				res = min(res, cap)
				r = cap - 1
			else:
				l = cap + 1
		return res


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		left = max(arr)
		right = sum(arr)
		ans = right
		if N == D:
			return max(arr)
		while left <= right:
			count = 0
			days = 1
			mid = (left + right) // 2
			for i in arr:
				count += i
				if count > mid:
					count = i
					days += 1
			if count > mid:
				days += 1
			if days <= D:
				right = mid - 1
				ans = mid
			else:
				left = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		low = max(arr)
		high = sum(arr)
		if N < D:
			return -1

		def isvalid(arr, N, D, mid):
			counter = 1
			sum = 0
			for i in arr:
				sum = sum + i
				if sum > mid:
					counter += 1
					sum = i
				if counter > D:
					return False
			return True
		res = -1
		while low <= high:
			mid = low + (high - low) // 2
			if isvalid(arr, N, D, mid) == True:
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def isValid(c):
			d = 1
			cap = 0
			for i in arr:
				if cap + i > c:
					cap = 0
					d += 1
				cap += i
			return True if d <= D else False
		low = max(arr)
		h = sum(arr)
		res = h
		while low <= h:
			mid = (h + low) // 2
			if isValid(mid):
				res = min(res, mid)
				h = mid - 1
			else:
				low = mid + 1
		return res


class Solution:

	def leastWeightCapacity(self, w, N, d):

		def f(m, w, d):
			v = 1
			n = 0
			for i in w:
				if n + i <= m:
					n += i
				else:
					n = i
					v += 1
			if v <= d:
				return 1
			return 0
		a = max(w)
		z = sum(w)
		c = 0
		while a <= z:
			m = (a + z) // 2
			if f(m, w, d):
				z = m - 1
				c = m
			else:
				a = m + 1
		return c


class Solution:

	def ispossible(self, arr, mid, days):
		d = 1
		sum2 = 0
		i = 0
		while i < len(arr):
			sum2 += arr[i]
			if sum2 > mid:
				d += 1
				sum2 = arr[i]
			i += 1
		return d <= days

	def leastWeightCapacity(self, arr, N, days):
		max1 = max(arr)
		sum1 = sum(arr)
		if N == days:
			return max1
		low = max1
		high = sum1
		res = 0
		while low <= high:
			mid = (low + high) // 2
			if self.ispossible(arr, mid, days):
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		weights = arr
		days = D
		single_el = -1
		total_el = 0
		for el in weights:
			single_el = max(single_el, el)
			total_el += el

		def find(mid, weights, days):
			d = 1
			sum = 0
			for el in weights:
				if sum + el > mid:
					d += 1
					sum = 0
				sum += el
			if d > days:
				return False
			else:
				return True
		ans = total_el
		while single_el <= total_el:
			mid = (single_el + total_el) // 2
			if find(mid, weights, days):
				ans = mid
				total_el = mid - 1
			else:
				single_el = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def fesible(arr, cap, d):
			sm = 0
			days = 0
			for weight in arr:
				if weight + sm <= cap:
					sm += weight
				else:
					days += 1
					sm = weight
			if sm > 0:
				days += 1
			return D >= days
		(low, high) = (max(arr), sum(arr))
		res = -1
		while low <= high:
			mid = (low + high) // 2
			if fesible(arr, mid, D):
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		(l, r) = (max(arr), sum(arr))

		def shippingDays(limit):
			(d, curr) = (1, 0)
			for w in arr:
				curr += w
				if curr > limit:
					d += 1
					curr = w
			return d
		while l < r:
			mid = (l + r) // 2
			if shippingDays(mid) <= D:
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def helper(self, arr, capacity):
		(load, days) = (0, 1)
		for w in arr:
			if load + w <= capacity:
				load += w
			else:
				days += 1
				load = w
		return days

	def leastWeightCapacity(self, arr, N, D):
		(l, r) = (max(arr), sum(arr))
		while l < r:
			capacity = l + r >> 1
			days = self.helper(arr, capacity)
			if days > D:
				l = capacity + 1
			else:
				r = capacity
		return l


class Solution:

	def ifPossible(self, weights, days, mid):
		day = 1
		weight_load = 0
		for i in range(len(weights)):
			weight_load += weights[i]
			if weight_load > mid:
				day += 1
				weight_load = weights[i]
		if day > days:
			return False
		return True

	def leastWeightCapacity(self, weights, N, days):
		(low, high) = (max(weights), sum(weights))
		res = -1
		while low <= high:
			mid = low + (high - low) // 2
			if self.ifPossible(weights, days, mid):
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		low = 1
		hi = sum(arr)
		ans = hi

		def rec(val):
			sumi = 0
			d = 0
			for i in arr:
				if i > val:
					return False
				if sumi + i <= val:
					sumi += i
				else:
					d += 1
					sumi = i
			if d >= D:
				return False
			return True
		while low <= hi:
			mid = (low + hi) // 2
			if rec(mid):
				ans = mid
				hi = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def check(arr, N, capacity, D):
			wt = 0
			days = 1
			for i in arr:
				if i > capacity:
					return False
				wt = wt + i
				if wt > capacity:
					days = days + 1
					wt = i
			if days > D:
				return False
			return True
		low = 0
		high = sum(arr)
		ans = 0
		mid = 0
		while low <= high:
			mid = int(low + (high - low) / 2)
			if check(arr, N, mid, D):
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def isValid(self, weight, n, D, mx):
		st = 1
		sum = 0
		for i in range(n):
			sum += weight[i]
			if sum > mx:
				st += 1
				sum = weight[i]
			if st > D:
				return False
		return True

	def leastWeightCapacity(self, arr, N, D):
		sum = 0
		for i in range(N):
			sum += arr[i]
		s = arr[0]
		for i in range(1, N):
			s = max(s, arr[i])
		e = sum
		res = -1
		while s <= e:
			mid = s + (e - s) // 2
			if self.isValid(arr, N, D, mid):
				res = mid
				e = mid - 1
			else:
				s = mid + 1
		return res


class Solution:

	def findDays(self, arr, D, capacity):
		arr_sum = 0
		days = 1
		for a in arr:
			arr_sum += a
			if arr_sum > capacity:
				days += 1
				arr_sum = a
		return days > D

	def leastWeightCapacity(self, arr, N, D):
		(left, right) = (max(arr), sum(arr))
		while left <= right:
			mid = left + right >> 1
			if self.findDays(arr, D, mid):
				left = mid + 1
			else:
				right = mid - 1
		return left


class Solution:

	def isPossibleDays(self, arr, N, D, mid):
		sum = 0
		days = 1
		for i in range(N):
			if sum + arr[i] <= mid:
				sum += arr[i]
			else:
				sum = arr[i]
				days += 1
		return days

	def leastWeightCapacity(self, arr, N, D):
		low = max(arr)
		high = sum(arr)
		ans = -1
		while low <= high:
			mid = (low + high) // 2
			if self.isPossibleDays(arr, N, D, mid) <= D:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, weights, N, days):
		i = max(weights)
		j = sum(weights)
		while i < j:
			mid = i + j >> 1
			summ = 0
			cou = 1
			for k in weights:
				if summ + k > mid:
					summ = 0
					cou += 1
				summ += k
			if cou <= days:
				j = mid
			else:
				i = mid + 1
		return i


def check(arr, n, m, mid):
	child = 1
	sumTill = 0
	for x in arr:
		if sumTill + x > mid:
			child += 1
			sumTill = 0
		sumTill += x
	return child <= m

def ans(arr, n, m):
	if n < m:
		return -1
	l = max(arr)
	r = sum(arr)
	res = 0
	while l <= r:
		mid = (l + r) // 2
		if check(arr, n, m, mid):
			res = mid
			r = mid - 1
		else:
			l = mid + 1
	return res

class Solution:

	def leastWeightCapacity(self, arr, N, D):
		return ans(arr, N, D)


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		low = max(arr)
		high = sum(arr)
		while low < high:
			mid = low + high >> 1
			(need, cap) = (1, 0)
			for i in range(N):
				if cap + arr[i] > mid:
					need += 1
					cap = 0
				cap += arr[i]
			if need > D:
				low = mid + 1
			else:
				high = mid
		return low


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		ans = float('INF')
		start = max(arr)
		end = sum(arr)
		if len(arr) <= D:
			return max(arr)
		while start <= end:
			m = (start + end) // 2
			days = 1
			count = 0
			for d in arr:
				count += d
				if count > m:
					days += 1
					count = d
			if days <= D:
				ans = m
				end = m - 1
			else:
				start = m + 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		r = sum(arr)
		l = max(r // D, max(arr))
		while l < r:
			m = (l + r) // 2
			need = 1
			cur = 0
			for w in arr:
				cur += w
				if cur > m:
					need += 1
					cur = w
			if need > D:
				l = m + 1
			else:
				r = m
		return l


class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def f(cap) -> bool:
			load = 0
			day = 1
			for w in arr:
				load += w
				if load > cap:
					load = w
					day += 1
					if day > D:
						return False
			return True
		l = max(arr)
		h = sum(arr)
		while l < h:
			m = (l + h) // 2
			if f(m):
				h = m
			else:
				l = m + 1
		return l


import math

class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def possible(mid, D):
			cap = mid
			days = 0
			for i in arr:
				if cap < i:
					days += 1
					cap = mid
					cap -= i
				else:
					cap -= i
			if cap < mid:
				days += 1
			if days <= D:
				return True
			return False
		s = max(arr)
		e = 10 ** 5
		while s <= e:
			mid = (s + e) // 2
			if possible(mid, D):
				e = mid - 1
			else:
				s = mid + 1
		return s


def isvalidship(mid, arr, D):
	capacity = 0
	Total_shipping_days = 1
	for i in range(len(arr)):
		if capacity + arr[i] <= mid:
			capacity += arr[i]
		else:
			Total_shipping_days += 1
			capacity = arr[i]
	if Total_shipping_days <= D:
		return True
	else:
		return False

class Solution:

	def leastWeightCapacity(self, arr, N, D):
		(lo, hi) = (max(arr), sum(arr))
		least_weight_capacity = 0
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			is_valid_ship_days = isvalidship(mid, arr, D)
			if is_valid_ship_days == True:
				least_weight_capacity = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return least_weight_capacity


class Solution:

	def leastWeightCapacity(self, arr, N, days):

		def helper(capacity):
			prev = 0
			ans = 0
			for num in arr:
				prev += num
				if prev > capacity:
					ans += 1
					prev = num
			return ans + 1 if prev > 0 else ans
		start = max(arr) - 1
		end = sum(arr)
		while end - start > 1:
			m = (end + start) // 2
			if helper(m) <= days:
				end = m
			else:
				start = m
		return end


class Solution:

	def check(self, arr, days, mid):
		count = 1
		sum_ = 0
		for w in arr:
			sum_ += w
			if sum_ > mid:
				count += 1
				if count > days:
					return False
				sum_ = w
		return True

	def leastWeightCapacity(self, arr, N, days):
		start = max(arr)
		end = sum(arr)
		while start <= end:
			mid = start + (end - start) // 2
			if self.check(arr, days, mid):
				end = mid - 1
			else:
				start = mid + 1
		return start


class Solution:

	def leastWeightCapacity(self, arr, n, d):

		def checker(poss, arr, n, d):
			total = 0
			days = 1
			for i in range(n):
				if arr[i] > mid:
					return False
				if total + arr[i] <= poss:
					total += arr[i]
				else:
					days += 1
					total = arr[i]
			return days <= d
		l = 1
		r = sum(arr)
		ans = -1
		if d == 1:
			return r
		while l <= r:
			mid = (l + r) // 2
			if checker(mid, arr, n, d):
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def solve(self, arr, capacity, D):
		count = 1
		su = 0
		for i in arr:
			if su + i <= capacity:
				su += i
			else:
				count += 1
				if count > D or i > capacity:
					return False
				su = i
		return True

	def leastWeightCapacity(self, arr, N, D):
		(start, end) = (1, sum(arr))
		ans = sum(arr)
		while start <= end:
			mid = (start + end) // 2
			if self.solve(arr, mid, D):
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
		return ans


def isValidShip(arr, mid, D):
	capacity = 0
	day = 1
	for i in range(len(arr)):
		if capacity + arr[i] <= mid:
			capacity += arr[i]
		else:
			day += 1
			capacity = arr[i]
	if day <= D:
		return True
	else:
		return False

class Solution:

	def leastWeightCapacity(self, arr, N, D):
		(lo, hi) = (max(arr), sum(arr))
		cap = 0
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			check = isValidShip(arr, mid, D)
			if check == True:
				cap = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return cap


class Solution:

	def isTrue(self, arr, n, d, m):
		c = 1
		p = 0
		for i in arr:
			if i + p <= m:
				p += i
			else:
				c += 1
				if c > d or i > m:
					return False
				p = i
		return True

	def leastWeightCapacity(self, arr, N, D):
		s = 0
		e = sum(arr)
		res = -1
		while s <= e:
			m = s + (e - s) // 2
			if self.isTrue(arr, N, D, m):
				res = m
				e = m - 1
			else:
				s = m + 1
		return res


def isValidDays(arr, mid, D):
	days = 1
	capacity = 0
	for i in range(len(arr)):
		if capacity + arr[i] <= mid:
			capacity += arr[i]
		else:
			days += 1
			capacity = arr[i]
	if days <= D:
		return True
	else:
		return False

class Solution:

	def leastWeightCapacity(self, arr, N, D):
		(lo, hi) = (max(arr), sum(arr))
		minCapaciy = 0
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			result = isValidDays(arr, mid, D)
			if result == True:
				minCapacity = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return minCapacity


def isValid(arr, mid, D):
	day = 1
	curr_sum = 0
	for i in range(len(arr)):
		if curr_sum + arr[i] <= mid:
			curr_sum += arr[i]
		else:
			day += 1
			curr_sum = arr[i]
	if day <= D:
		return True
	else:
		return False

class Solution:

	def leastWeightCapacity(self, arr, N, D):
		(lo, hi) = (max(arr), sum(arr))
		ans = 0
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			result = isValid(arr, mid, D)
			if result == True:
				ans = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return ans


class Solution:

	def no_of_days(self, weights, capacity):
		(load, days) = (0, 1)
		for w in weights:
			if load + w <= capacity:
				load += w
			else:
				load = w
				days += 1
		return days

	def leastWeightCapacity(self, arr, N, D):
		(l, r) = (max(arr), sum(arr))
		while l <= r:
			mid = (l + r) // 2
			days = self.no_of_days(arr, mid)
			if days > D:
				l = mid + 1
			else:
				r = mid - 1
		return l


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		if N == D:
			return max(arr)
		(a, b) = (max(arr), sum(arr))
		while a < b:
			mid = (a + b) // 2
			(ct, days) = (0, 1)
			for i in arr:
				ct += i
				if ct > mid:
					ct = i
					days += 1
			if days <= D:
				b = mid
			else:
				a = mid + 1
		return b


class Solution:

	def isvalid(self, weight, mx, d):
		s = 0
		st = 0
		for i in range(len(weight)):
			s += weight[i]
			if s > mx:
				st += 1
				s = weight[i]
			if st >= d:
				return False
		return True

	def binarysearch(self, weight, d, l, r):
		if l <= r:
			mid = (l + r) // 2
			if self.isvalid(weight, mid, d):
				return self.binarysearch(weight, d, l, mid - 1)
			else:
				return self.binarysearch(weight, d, mid + 1, r)
		return l

	def leastWeightCapacity(self, arr, N, D):
		return self.binarysearch(arr, D, max(arr), sum(arr))


def isPossible(arr, mid, d):
	countDays = 1
	res = 0
	for i in range(len(arr)):
		if arr[i] > mid:
			return False
		if arr[i] + res > mid:
			countDays += 1
			res = arr[i]
			if countDays > d:
				return False
		else:
			res += arr[i]
	return True

class Solution:

	def leastWeightCapacity(self, arr, N, D):
		high = sum(arr)
		low = 0
		ans = 10000000000
		while low <= high:
			mid = (low + high) // 2
			if isPossible(arr, mid, D):
				ans = min(ans, mid)
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		low = max(arr)
		high = 100000
		while low <= high:
			mid = int((low + high) // 2)
			noOfdaysToShip = self.calcDaystoShipForBoatWeight(arr, N, D, mid)
			if noOfdaysToShip > D:
				low = mid + 1
			else:
				high = mid - 1
		return low

	def calcDaystoShipForBoatWeight(self, arr, N, D, weight):
		tempWeight = weight
		days = i = 0
		while i < N:
			if tempWeight + arr[i] <= weight:
				tempWeight += arr[i]
			else:
				tempWeight = arr[i]
				days += 1
			i += 1
			if days > D:
				break
		return days


def isPossible(a, k, l):
	(count, curr) = (1, 0)
	for i in a:
		if i > l:
			return False
		curr += i
		if curr > l:
			curr = i
			count += 1
	return count <= k

class Solution:

	def leastWeightCapacity(self, arr, N, D):
		(st, en) = (0, sum(arr))
		ans = 0
		while st <= en:
			mid = (st + en) // 2
			curr = isPossible(arr, D, mid)
			if curr:
				en = mid - 1
				ans = mid
			else:
				st = mid + 1
		return ans


import math

class Solution:

	def leastWeightCapacity(self, piles, n, H):
		ans = sum(piles)
		s = max(piles)
		e = ans
		while s <= e:
			mid = (s + e) // 2
			temp = 0
			count = 1
			for i in piles:
				temp += i
				if temp > mid:
					count += 1
					temp = i
			if count > H:
				s = mid + 1
			else:
				ans = min(ans, mid)
				e = mid - 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, n, d):
		sm = sum(arr)
		mx = max(arr)
		ii = mx
		j = sm
		ans = 0
		while ii <= j:
			mid = (ii + j) // 2
			s = 1
			wt = 0
			for i in range(n):
				wt = wt + arr[i]
				if wt > mid:
					s = s + 1
					wt = arr[i]
					if wt > mid:
						wt = 0
						s = s + 1
			if s <= d:
				ans = mid
				j = mid - 1
			else:
				ii = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, weights, N, days):
		(l, r) = (max(weights), sum(weights))
		capacity = r
		while l <= r:
			cur_cap = (l + r) // 2
			(shipment, ship_days) = (0, 1)
			for w in weights:
				if shipment + w > cur_cap:
					ship_days += 1
					shipment = 0
				shipment += w
			if ship_days <= days:
				capacity = min(capacity, cur_cap)
				r = cur_cap - 1
			else:
				l = cur_cap + 1
		return capacity


class Solution:

	def isvalid(self, arr, cap, N, D):
		d = 1
		summ = 0
		for i in range(0, N):
			summ += arr[i]
			if summ > cap:
				summ = arr[i]
				d += 1
		if d <= D:
			return True
		return False

	def leastWeightCapacity(self, arr, N, D):
		l = max(arr)
		h = sum(arr)
		ans = 0
		while l <= h:
			mid = (l + h) // 2
			if self.isvalid(arr, mid, N, D):
				ans = mid
				h = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		l = max(arr)
		r = sum(arr)
		while l < r:
			mid = (l + r) // 2
			if self.can_ship(mid, arr, D):
				r = mid
			else:
				l = mid + 1
		return r

	def can_ship(self, candidate, arr, D):
		cur_weight = 0
		days_taken = 1
		for weight in arr:
			cur_weight += weight
			if cur_weight > candidate:
				days_taken += 1
				cur_weight = weight
		return days_taken <= D


class Solution:

	def leastWeightCapacity(self, arr, n, d):
		ans = 999999
		high = sum(arr)
		low = max(arr)
		while high >= low:
			mid = (low + high) // 2
			su = 0
			count = 1
			for i in range(n):
				if su + arr[i] <= mid:
					su += arr[i]
				else:
					su = arr[i]
					count += 1
			if count == d:
				ans = mid
				high = mid - 1
			elif count < d:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		r = sum(arr)
		l = max(arr)
		ans = 0
		while l <= r:
			m = (l + r) // 2
			cap = 0
			days = 0
			for i in arr:
				cap += i
				if cap > m:
					cap = i
					days += 1
			if cap <= m:
				days += 1
			if days > D:
				l = m + 1
			else:
				ans = m
				r = m - 1
		return l


class Solution:

	def leastWeightCapacity(self, weights, N, D):

		def feasible(capacity) -> bool:
			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, 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 leastWeightCapacity(self, arr, N, D):
		return self.binarysearch(arr, N, D)

	def binarysearch(self, arr, N, days):
		start = max(arr)
		end = sum(arr)
		res = -1
		while start <= end:
			mid = start + (end - start) // 2
			if self.valid(arr, N, days, mid) == True:
				res = mid
				end = mid - 1
			else:
				start = mid + 1
		return res

	def valid(self, arr, N, days, mid):
		capacity = 1
		su = 0
		for i in range(0, N):
			su += arr[i]
			if su > mid:
				capacity += 1
				su = arr[i]
		if capacity > days:
			return False
		return True


class Solution:

	def leastWeightCapacity(self, arr, N, D):

		def isValid(mid):
			count = 1
			total = 0
			for i in range(len(arr)):
				if arr[i] > mid:
					return False
				if total + arr[i] > mid:
					total = arr[i]
					count += 1
				else:
					total += arr[i]
			return count <= D
		left = 1
		right = sum(arr)
		result = -1
		while left <= right:
			mid = left + right >> 1
			if isValid(mid):
				result = mid
				right = mid - 1
			else:
				left = mid + 1
		return result


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		l = max(arr)
		h = sum(arr)
		weight = sum(arr)
		while l <= h:
			mid = (l + h) // 2
			day = 0
			sm = 0
			i = 0
			while i < N:
				sm += arr[i]
				if sm > mid:
					sm -= arr[i]
					day += 1
					sm = arr[i]
				if i == N - 1:
					day += 1
				i += 1
			if day <= D:
				weight = min(weight, mid)
				h = mid - 1
			else:
				l = mid + 1
		return weight


class Solution:

	def leastWeightCapacity(self, arr, N, D):
		(l, r) = (max(arr), sum(arr))

		def check(val):
			s = 0
			c = 1
			m = 0
			for a in arr:
				if s + a > val:
					c += 1
					s = 0
				s += a
			return c
		ans = 1000000000.0
		while l < r:
			mid = (l + r) // 2
			x = check(mid)
			if x > D:
				l = mid + 1
			else:
				r = mid
		return l


def nDays(arr, mid):
	days = 1
	cap = mid
	for i in arr:
		if cap >= i:
			cap -= i
		else:
			days += 1
			cap = mid
			cap -= i
	return days

class Solution:

	def leastWeightCapacity(self, arr, N, D):
		low = max(arr)
		high = sum(arr)
		ans = high
		while low <= high:
			mid = low + (high - low) // 2
			days = nDays(arr, mid)
			if days <= D:
				ans = min(ans, mid)
				high = mid - 1
			else:
				low = mid + 1
		return ans


def solve(A, mid, D):
	c = 0
	pref = 0
	for i in range(len(A)):
		pref += A[i]
		if pref < mid:
			continue
		if pref == mid:
			c += 1
			pref = 0
			continue
		c += 1
		pref = A[i]
	while pref > 0:
		pref -= mid
		c += 1
	return c <= D

class Solution:

	def leastWeightCapacity(self, A, N, D):
		l = max(A)
		r = sum(A)
		if N == 1:
			return r
		ans = r
		while l <= r:
			mid = l + r >> 1
			if solve(A, mid, D):
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans