Given an array arr[] of N elements and a number K. Split the given array into K subarrays such that the maximum subarray sum achievable out of K subarrays formed is minimum possible. Find that possible subarray sum.
Example 1:
Input:
N = 4, K = 3
arr[] = {1, 2, 3, 4}
Output: 4
Explanation:
Optimal Split is {1, 2}, {3}, {4}.
Maximum sum of all subarrays is 4,
which is minimum possible for 3 splits. 
Example 2:
Input:
N = 3, K = 2
A[] = {1, 1, 2}
Output:
2
Explanation:
Splitting the array as {1,1} and {2} is optimal.
This results in a maximum sum subarray of 2.
 
Your Task:
The task is to complete the function splitArray() which returns the maximum sum subarray after splitting the array into K subarrays such that maximum sum subarray is minimum possible.
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ K ≤ N
1 ≤ arr[i] ≤ 10^{4}
Expected Time Complexity: O(N*log(sum(arr))).
Expected Auxiliary Space: O(1).

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def splitArray(self, arr, N, K):

        # code here 

Solutions:
class Solution:

	def splitArray(self, arr, n, K):

		def fun(mid):
			subarray = 0
			curSum = 0
			for i in arr:
				curSum += i
				if curSum > mid:
					subarray += 1
					curSum = i
			return subarray + 1 <= K
		(l, r) = (max(arr), sum(arr))
		res = r
		while l <= r:
			mid = l + r >> 1
			if fun(mid):
				res = mid
				r = mid - 1
			else:
				l = mid + 1
		return res


class Solution:

	def splitArray(self, arr, N, K):
		(left, right) = (max(arr), sum(arr))
		while left < right:
			mid = (left + right) // 2
			(curSum, count) = (0, 0)
			for num in arr:
				curSum += num
				if curSum > mid:
					curSum = num
					count += 1
			if count >= K:
				left = mid + 1
			else:
				right = mid
		return right


class Solution:

	def splitArray(self, arr, N, K):
		(lo, hi) = (max(arr), sum(arr))
		ans_candidate = lo
		while lo <= hi:
			potential_maximum = lo + (hi - lo) // 2
			subarrays_count = 1
			current_sum = 0
			for a in arr:
				current_sum += a
				if current_sum > potential_maximum:
					current_sum = a
					subarrays_count += 1
			if subarrays_count <= K:
				ans_candidate = potential_maximum
				hi = potential_maximum - 1
			else:
				lo = potential_maximum + 1
		return ans_candidate


class Solution:

	def splitArray(self, arr, N, K):

		def checkPartition(arr, partsum):
			sum1 = 0
			count = 1
			for i in arr:
				if sum1 + i > partsum:
					count = count + 1
					sum1 = i
					continue
				sum1 = sum1 + i
			if count <= K:
				return True
			return False
		(i, j) = (max(arr), sum(arr))
		res = -1
		while j >= i:
			mid = (i + j) // 2
			x = checkPartition(arr, mid)
			if x:
				res = mid
				j = mid - 1
			else:
				i = mid + 1
		return res


class Solution:

	def isPossible(self, arr, N, K, mid):
		count = 1
		total_sum = 0
		for i in range(N):
			if total_sum + arr[i] <= mid:
				total_sum += arr[i]
			else:
				count += 1
				if count > K or arr[i] > mid:
					return False
				else:
					total_sum = arr[i]
		return True

	def splitArray(self, arr, N, K):
		start = 0
		total = 0
		for i in arr:
			total += i
		end = total
		ans = -1
		mid = start + (end - start) // 2
		while start <= end:
			if self.isPossible(arr, N, K, mid):
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
			mid = start + (end - start) // 2
		return ans


class Solution:

	def splitArray(self, arr, N, K):

		def canSplit(largest):
			subarray = 0
			curSum = 0
			for i in range(N):
				curSum += arr[i]
				if curSum > largest:
					subarray += 1
					curSum = arr[i]
			return subarray + 1 <= K
		left = max(arr)
		right = sum(arr)
		while left <= right:
			mid = (left + right) // 2
			if canSplit(mid):
				ans = mid
				right = mid - 1
			else:
				left = mid + 1
		return ans


class Solution:

	def splitArray(self, arr, N, K):
		s = min(arr) - 1
		e = sum(arr)
		while 1 < e - s:
			m = (e + s) // 2
			i = 0
			j = 0
			sub_sum = 0
			success = True
			while j < N:
				if m < arr[j]:
					success = False
					break
				if sub_sum + arr[j] <= m:
					sub_sum += arr[j]
				else:
					sub_sum = arr[j]
					i += 1
				j += 1
				if i == K:
					success = False
					break
			if success:
				e = m
			else:
				s = m
		return e


class Solution:

	def check(self, mid, array, n, K):
		count = 0
		sum = 0
		for i in range(n):
			if array[i] > mid:
				return False
			sum += array[i]
			if sum > mid:
				count += 1
				sum = array[i]
		count += 1
		if count <= K:
			return True
		return False

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


class Solution:

	def splitArray(self, arr, N, K):

		def canSplit(n):
			sub = 0
			cur = 0
			for i in arr:
				cur += i
				if cur > n:
					sub += 1
					cur = i
			return sub + 1 <= K
		(l, r) = (arr[0], 0)
		for i in range(N):
			l = max(l, arr[i])
			r += arr[i]
		res = r
		while l <= r:
			mid = l + (r - l) // 2
			if canSplit(mid):
				res = mid
				r = mid - 1
			else:
				l = mid + 1
		return res


import heapq

class Solution:

	def splitArray(self, arr, N, K):
		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 <= K:
				high = mid
			else:
				low = mid + 1
		return high


class Solution:

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

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


class Solution:

	def splitArray(self, arr, N, K):

		def check(arr, N, K, mid):
			cur_sum = 0
			i = 0
			while i < N:
				if cur_sum + arr[i] <= mid:
					cur_sum += arr[i]
				elif cur_sum + arr[i] > mid and arr[i] <= mid and (K > 1):
					K -= 1
					cur_sum = arr[i]
				else:
					return False
				i += 1
			return True
		hi = sum(arr)
		lo = 0
		ans = 0
		while lo <= hi:
			mid = (lo + hi) // 2
			if check(arr, N, K, mid):
				ans = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return ans


class Solution:

	def isPossible(self, nums, mid, k):
		(subarr_count, subarr_sum) = (1, 0)
		for i in range(len(nums)):
			subarr_sum += nums[i]
			if subarr_sum > mid:
				subarr_count += 1
				subarr_sum = nums[i]
		if subarr_count <= k:
			return True
		else:
			return False

	def splitArray(self, nums, n, k):
		if k > len(nums):
			return -1
		res = -1
		(low, high) = (max(nums), sum(nums))
		while low <= high:
			mid = low + (high - low) // 2
			if self.isPossible(nums, mid, k):
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


class Solution:

	def CanAllocateArrays(self, limit, arr, k):
		arr_count = 1
		total = 0
		for i in range(len(arr)):
			total += arr[i]
			if total > limit:
				arr_count += 1
				total = arr[i]
		if arr_count <= k:
			return True
		else:
			return False

	def splitArray(self, arr, N, K):
		l = max(arr)
		h = sum(arr)
		ans = -1
		while l <= h:
			mid = l + (h - l) // 2
			if self.CanAllocateArrays(mid, arr, K):
				ans = mid
				h = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def splitArray(self, arr, N, K):

		def Split(largest):
			count = 0
			curSum = 0
			for i in arr:
				curSum += i
				if curSum > largest:
					count += 1
					curSum = i
			if count + 1 <= K:
				return count
		(l, r) = (max(arr), sum(arr))
		res = r
		while l <= r:
			mid = (l + r) // 2
			if Split(mid):
				res = mid
				r = mid - 1
			else:
				l = mid + 1
		return res


class Solution:

	def splitArray(self, arr, n, k):
		s = sum(arr)
		low = s // k
		high = s
		mn = 10 ** 9
		while low <= high:
			mx = 0
			mid = (low + high) // 2
			c = 1
			sm = 0
			for i in range(n):
				if sm + arr[i] <= mid:
					sm += arr[i]
				else:
					c += 1
					mx = max(mx, sm)
					sm = arr[i]
			mx = max(mx, sm)
			if c <= k:
				mn = min(mn, mx)
				high = mid - 1
			else:
				low = mid + 1
		return mn


class Solution:

	def findPartitions(self, arr, ans, n):
		k = 1
		rem_ans = ans
		for i in range(n):
			if arr[i] <= rem_ans:
				rem_ans = rem_ans - arr[i]
			else:
				k = k + 1
				rem_ans = ans
				rem_ans = rem_ans - arr[i]
		return k

	def splitArray(self, arr, n, k):
		ans = None
		maximum_element = arr[0]
		TotalSum = arr[0]
		for i in range(1, n):
			if maximum_element < arr[i]:
				maximum_element = arr[i]
			TotalSum += arr[i]
		start = maximum_element
		end = TotalSum
		while start <= end:
			mid = (start + end) // 2
			partitions = self.findPartitions(arr, mid, n)
			if partitions <= k:
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
		return ans


class Solution:

	def splitArray(self, arr, N, K):
		(l, r) = (max(arr), sum(arr))
		while l < r:
			mid = (l + r) // 2
			(cursum, count) = (0, 0)
			for num in arr:
				cursum += num
				if cursum > mid:
					cursum = num
					count += 1
			if count >= K:
				l = mid + 1
			else:
				r = mid
		return r


class Solution:

	def splitArray(self, arr, N, K):
		a = max(arr)
		b = sum(arr)
		while a < b:
			m = (a + b) // 2
			cs = 0
			c = 0
			for i in arr:
				cs += i
				if cs > m:
					cs = i
					c += 1
			if c >= K:
				a = m + 1
			else:
				b = m
		return b


class Solution:

	def splitArray(self, A, N, K):
		(l, r) = (max(A), sum(A))
		while l < r:
			m = l + r >> 1
			c = 1
			s = 0
			for i in A:
				s += i
				if s > m:
					c += 1
					s = i
			if c <= K:
				r = m
			else:
				l = m + 1
		return r


class Solution:

	def check_possible(self, mid, arr, K):
		curr_sum = 0
		counter = K
		buckets = [0 for _ in range(K)]
		for val in arr:
			if counter <= 0:
				return False
			if val > mid:
				return False
			if curr_sum + val > mid:
				curr_sum = val
				counter -= 1
			else:
				curr_sum += val
		if counter > 0:
			return True
		return False

	def splitArray(self, arr, N, K):
		sum_arr = 0
		for val in arr:
			sum_arr += val
		left = 0
		right = sum_arr
		printing_counter = 100
		while right - left > 1:
			mid = int((right + left) / 2)
			possible = self.check_possible(mid, arr, K)
			if possible:
				right = mid
			else:
				left = mid
		if self.check_possible(left, arr, K):
			return left
		else:
			return right


class Solution:

	def splitArray(self, arr, N, K):
		sum = 0
		if N < K:
			return -1
		for i in range(N):
			sum += arr[i]
		(start, end) = (0, sum)
		result = 10 ** 9
		while start <= end:
			mid = (start + end) // 2
			if self.isPossible(arr, N, K, mid):
				result = mid
				end = mid - 1
			else:
				start = mid + 1
		return result

	def isPossible(self, arr, n, k, curr_min):
		partsRequired = 1
		curr_sum = 0
		for i in range(n):
			if arr[i] > curr_min:
				return False
			if curr_sum + arr[i] > curr_min:
				partsRequired += 1
				curr_sum = arr[i]
				if partsRequired > k:
					return False
			else:
				curr_sum += arr[i]
		return True


class Solution:

	def check(self, arr, target, k):
		curr = 0
		count = 1
		for x in arr:
			if curr + x > target:
				curr = 0
				count += 1
			curr += x
		return count <= k

	def splitArray(self, arr, N, k):
		if N < K:
			return -1
		(left, right) = (max(arr), sum(arr))
		res = 0
		while left <= right:
			mid = (left + right) // 2
			ch = self.check(arr, mid, k)
			if ch:
				res = mid
				right = mid - 1
			else:
				left = mid + 1
		return res


class Solution:

	def splitArray(self, arr, N, K):

		def is_sum_poss(max_sum):
			index = 0
			sub_arr = 0
			curr_sum = 0
			while index < N:
				if curr_sum + arr[index] > max_sum:
					curr_sum = arr[index]
					sub_arr += 1
				else:
					curr_sum += arr[index]
				index += 1
			return sub_arr + 1 if curr_sum != 0 else 0
		max_sum = sum(arr)
		l = max(arr)
		h = max_sum
		while l < h:
			mid = l + (h - l) // 2
			poss_sub_arr = is_sum_poss(mid)
			if poss_sub_arr <= K:
				h = mid
			else:
				l = mid + 1
		return l


class Solution:

	def splitArray(self, arr, N, K):
		(left, right) = (max(arr), sum(arr))
		res = right

		def canSplit(largest):
			subarray = 1
			currSum = 0
			for num in arr:
				currSum += num
				if currSum > largest:
					currSum = num
					subarray += 1
			return subarray <= K
		while left <= right:
			mid = (left + right) // 2
			if canSplit(mid):
				res = mid
				right = mid - 1
			else:
				left = mid + 1
		return res


class Solution:

	def splitArray(self, arr, N, K):

		def check(arr, N, K, mid):
			curr_sum = 0
			num_subarrays = 1
			for i in range(N):
				curr_sum += arr[i]
				if curr_sum > mid:
					num_subarrays += 1
					curr_sum = arr[i]
				if num_subarrays > K:
					return False
			return True
		low = max(arr)
		high = sum(arr)
		while low < high:
			mid = (low + high) // 2
			if check(arr, N, K, mid):
				high = mid
			else:
				low = mid + 1
		return low


import math

def check(a, mid, k):
	count = 0
	sum = 0
	for x in a:
		if x > mid:
			return False
		sum += x
		if sum > mid:
			count += 1
			sum = x
	count += 1
	return count <= k

class Solution:

	def splitArray(self, a, n, k):
		left = 1
		right = sum(arr)
		ans = 0
		while left <= right:
			mid = (left + right) // 2
			if check(a, mid, k):
				right = mid - 1
				ans = mid
			else:
				left = mid + 1
		return ans


class Solution:

	def splitArray(self, arr, N, K):

		def findSplit(target):
			splitted = 1
			summ = 0
			for n in arr:
				summ += n
				if summ > target:
					splitted += 1
					if splitted > K:
						return False
					summ = n
			return True
		l = max(arr)
		r = sum(arr)
		while l <= r:
			mid = (l + r) // 2
			if findSplit(mid):
				r = mid - 1
			else:
				l = mid + 1
		return l


class Solution:

	def splitArray(self, arr, N, K):
		mi = max(arr)
		ma = sum(arr)
		while mi <= ma:
			mid = (mi + ma) // 2
			subarr = 0
			su = 0
			for i in range(N):
				su += arr[i]
				if su > mid:
					subarr += 1
					su = arr[i]
			if subarr + 1 <= K:
				ans = mid
				ma = mid - 1
			else:
				mi = mid + 1
		return ans


class Solution:

	def splitArray(self, arr, N, K):
		return my_answer(arr, N, K)

def my_answer(arr, N, K):
	max_ans = sum(arr)
	min_ans = max(arr)
	while min_ans < max_ans:
		mid_ans = (min_ans + max_ans) // 2
		k_needed = 1
		subarray_sum = 0
		for val in arr:
			subarray_sum += val
			if subarray_sum > mid_ans:
				k_needed += 1
				subarray_sum = val
		if k_needed <= K:
			max_ans = mid_ans
		else:
			assert k_needed > K
			min_ans = mid_ans + 1
	assert min_ans == max_ans
	return min_ans


class Solution:

	def isMidPossibleAns(self, mid, arr, n, K):
		count = 1
		total = 0
		for i in range(n):
			if arr[i] > mid:
				return False
			total += arr[i]
			if total > mid:
				count += 1
				total = arr[i]
		return count <= K

	def splitArray(self, arr, N, K):
		(low, high, ans) = (0, sum(arr), -1)
		while low <= high:
			mid = low + (high - low) // 2
			if self.isMidPossibleAns(mid, arr, N, K):
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def ispossible(self, arr, curr, m):
		csum = 0
		stu = 1
		for i in range(len(arr)):
			if arr[i] > curr:
				return False
			if csum + arr[i] > curr:
				stu += 1
				csum = arr[i]
				if stu > m:
					return False
			else:
				csum += arr[i]
		return True

	def binarysearch(self, arr, m, l, r):
		if l <= r:
			mid = (l + r) // 2
			if self.ispossible(arr, mid, m):
				return self.binarysearch(arr, m, l, mid - 1)
			else:
				return self.binarysearch(arr, m, mid + 1, r)
		return l

	def splitArray(self, arr, N, K):
		return self.binarysearch(arr, K, 0, sum(arr))


class Solution:

	def ispossible(self, mid, arr, k):
		part = 0
		n = len(arr)
		currsum = 0
		for i in range(n):
			currsum += arr[i]
			if currsum > mid:
				part += 1
				currsum = arr[i]
		part += 1
		if part <= k:
			return True
		return False

	def splitArray(self, arr, N, K):
		minsum = max(arr)
		maxsum = sum(arr)
		low = minsum
		high = maxsum
		res = 0
		while low <= high:
			mid = (low + high) // 2
			if self.ispossible(mid, arr, K):
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


def check(arr, k, n, mid):
	val = 0
	cnt = 0
	for i in range(n):
		val += arr[i]
		if val > mid:
			val = arr[i]
			cnt += 1
			if cnt == k and i < n:
				return False
	return True

class Solution:

	def splitArray(self, arr, n, k):
		l = 0
		h = 0
		for i in arr:
			if l < i:
				l = i
			h += i
		while l <= h:
			mid = (l + h) // 2
			if check(arr, k, n, mid):
				h = mid - 1
			else:
				l = mid + 1
		return l


class Solution:

	def splitArray(self, arr, N, K):
		start = max(arr)
		end = 0
		for i in arr:
			end += i
		mid = 0
		ans = 0
		while start <= end:
			mid = (start + end) // 2
			count = 0
			m_sum = 0
			for i in arr:
				if i > mid:
					return False
				m_sum += i
				if m_sum > mid:
					count += 1
					m_sum = i
			count += 1
			if count <= K:
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
		return ans


class Solution:

	def splitArray(self, arr, N, K):
		l = None
		r = 0
		ans = 0
		for x in arr:
			if l is None:
				l = x
			else:
				l = max(l, x)
			r += x
		while l <= r:
			mid = (l + r) // 2
			num = 0
			cursum = 0
			maxsum = 0
			for x in arr:
				if cursum + x <= mid:
					cursum += x
				else:
					num += 1
					cursum = x
			num += 1
			if num <= K:
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def check(self, arr, n, k, target):
		total_sum = 0
		c = 0
		for i in range(n):
			if arr[i] > target:
				return 0
			total_sum += arr[i]
			if total_sum > target:
				total_sum = arr[i]
				c += 1
		c += 1
		if c <= k:
			return True
		return False

	def splitArray(self, arr, n, k):
		low = max(arr)
		high = sum(arr)
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			if self.check(arr, n, k, mid):
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def splitArray(self, nums, N, K):
		(lo, hi) = (max(nums), sum(nums))
		while lo < hi:
			mid = (lo + hi) // 2
			(tot, cnt) = (0, 1)
			for num in nums:
				if tot + num <= mid:
					tot += num
				else:
					tot = num
					cnt += 1
			if cnt > K:
				lo = mid + 1
			else:
				hi = mid
		return hi


class Solution:

	def splitArray(self, arr, N, K):

		def cansplit(m):
			nonlocal K, arr
			s = 0
			cnt = 1
			for i in arr:
				s += i
				if s > m:
					cnt += 1
					s = i
			return cnt <= K
		(lo, hi) = (max(arr), sum(arr) + 1)
		while lo < hi:
			mi = lo + (hi - lo) // 2
			if cansplit(mi):
				hi = mi
			else:
				lo = mi + 1
		return lo


class Solution:

	def valid(self, mid, arr, N, K):
		count = 0
		ssum = 0
		for i in range(N):
			if arr[i] > mid:
				return False
			ssum += arr[i]
			if ssum > mid:
				count += 1
				ssum = arr[i]
		count += 1
		if count <= K:
			return True
		return False

	def splitArray(self, arr, N, K):
		start = max(arr)
		end = sum(arr)
		ans = 0
		while start <= end:
			mid = (start + end) // 2
			if self.valid(mid, arr, N, K):
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
		return ans


class Solution:

	def splitArray(self, arr, n, k):
		st = max(arr)
		end = sum(arr)
		cnt = 0
		ans = end + 1
		if k == 1:
			return end
		if k == n:
			return st
		while st <= end:
			mid = (st + end) // 2
			sm = 0
			cnt = 0
			for i in range(n):
				sm += arr[i]
				if sm == mid:
					sm = 0
					cnt += 1
				elif sm > mid:
					sm = arr[i]
					cnt += 1
					if i == n - 1:
						cnt += 1
				elif i == n - 1 and sm != 0:
					cnt += 1
			if cnt > k:
				st = mid + 1
			else:
				if 1:
					ans = min(ans, mid)
				end = mid - 1
		return ans


class Solution:

	def splitArray(self, arr, N, K):

		def canSplit(maximum):
			part = 1
			curSum = 0
			for n in arr:
				if n > maximum:
					return False
				if curSum + n > maximum:
					part += 1
					curSum = n
				else:
					curSum += n
			return part <= K
		low = max(arr)
		high = sum(arr)
		if K == 1:
			return high
		if K == N:
			return low
		ans = high
		while low <= high:
			mid = low + high >> 1
			if canSplit(mid):
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


import numpy as np

class Solution:

	def splitArray(self, arr, N, K):
		np_arr = np.array(arr)
		left = np_arr.max()
		right = np_arr.sum()
		while left <= right:
			mid = (left + right) // 2
			sum = 0
			subarr = 1
			for i in range(len(arr)):
				sum += arr[i]
				if sum <= mid:
					pass
				else:
					subarr += 1
					sum = arr[i]
			if subarr <= K:
				right = mid - 1
			else:
				left = mid + 1
		return left


class Solution:

	def splitArray(self, arr, N, K):
		low = max(arr)
		high = int()
		for i in arr:
			high += i
		if K > N:
			return -1
		while low <= high:
			mid = (high - low) // 2 + low
			cuts = 1
			sum = 0
			for ele in arr:
				sum += ele
				if sum > mid:
					sum = ele
					cuts += 1
			if cuts > K:
				low = mid + 1
			else:
				high = mid - 1
		return high + 1


def check(stack, k, target) -> bool:
	n = len(arr)
	j = n - 1
	need = target
	if k == n:
		if target >= max(stack):
			return True
		else:
			return False
	for i in range(k):
		if j < 0:
			return True
		while need > 0:
			if stack[j] > target:
				return False
			if stack[j] > need:
				break
			need -= stack[j]
			j -= 1
			if j < 0:
				break
		need = target
	if j >= 0:
		return False
	return True

def bin(arr, k, low, high):
	mid = (low + high) // 2
	if high == low:
		return low
	if check(arr, k, mid) == True:
		return bin(arr, k, low, mid)
	else:
		return bin(arr, k, mid + 1, high)

class Solution:

	def splitArray(self, arr, N, K):
		return bin(arr, K, 1, sum(arr))


class Solution:

	def isvalid(self, max_val, arr, K):
		co = 0
		curr = 0
		for i in arr:
			if curr + i > max_val:
				curr = i
				co += 1
			else:
				curr += i
		if curr <= max_val:
			co += 1
		return co <= K

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


class Solution:

	def splitArray(self, arr, N, k):

		def cansplit(m):
			nonlocal k, arr
			s = 0
			cnt = 1
			for e in arr:
				s += e
				if s > m:
					cnt += 1
					s = e
			return cnt <= k
		(low, high) = (max(arr), sum(arr))
		ans = 0
		while low <= high:
			mid = low + high >> 1
			if cansplit(mid):
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def __init__(self):
		self.res = -10000

	def binary_search(self, arr, sum_search):
		subarray = 0
		sum1 = 0
		for num in arr:
			sum1 += num
			if sum1 > sum_search:
				subarray += 1
				sum1 = num
		return subarray + 1 <= self.K

	def recursion(self, arr):
		if self.res != -10000:
			return
		if self.low > self.high:
			self.res = self.low
			return
		sum_search = self.low + self.high >> 1
		if self.binary_search(arr, sum_search):
			self.high = sum_search - 1
			self.recursion(arr)
		else:
			self.low = sum_search + 1
			self.recursion(arr)
		return

	def splitArray(self, arr, N, K):
		self.K = K
		if K == 1:
			return sum(arr)
		self.low = max(arr)
		self.high = sum(arr)
		self.recursion(arr)
		return self.res


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

class Solution:

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


class Solution:

	def __init__(self):
		self.res = -10000

	def binary_search(self, arr, sum_search):
		subarray = 0
		sum1 = 0
		for num in arr:
			sum1 += num
			if sum1 > sum_search:
				subarray += 1
				sum1 = num
		return subarray + 1 <= self.K

	def recursion(self, arr):
		print(self.low, self.high)
		if self.low == self.high:
			self.res = self.low
			return
		sum_search = int((self.low + self.high) / 2) + 1
		if self.binary_search(arr, sum_search):
			self.high = sum_search - 1
			self.recursion(arr)
		else:
			self.low = sum_search + 1
			self.recursion(arr)
		return

	def splitArray(self, arr, N, K):
		self.K = K
		if K == 1:
			return sum(arr)
		self.low = max(arr)
		self.high = sum(arr)
		while self.low <= self.high:
			mid = self.low + self.high >> 1
			if self.binary_search(arr, mid):
				self.res = mid
				self.high = mid - 1
			else:
				self.low = mid + 1
		return self.res


class Solution:

	def __init__(self):
		self.res = -10000

	def binary_search(self, arr, sum_search):
		subarray = 0
		sum1 = 0
		for num in arr:
			sum1 += num
			if sum1 > sum_search:
				subarray += 1
				sum1 = num
		return subarray + 1 <= self.K

	def recursion(self, arr):
		print(self.low, self.high)
		if self.low == self.high:
			self.res = self.low
			return
		sum_search = int((self.low + self.high) / 2) + 1
		if self.binary_search(arr, sum_search):
			self.high = sum_search - 1
			self.recursion(arr)
		else:
			self.low = sum_search + 1
			self.recursion(arr)
		return

	def splitArray(self, arr, n, K):

		def fun(mid):
			subarray = 0
			curSum = 0
			for i in arr:
				curSum += i
				if curSum > mid:
					subarray += 1
					curSum = i
			return subarray + 1 <= K
		(l, r) = (max(arr), sum(arr))
		res = r
		while l <= r:
			mid = l + r >> 1
			if fun(mid):
				res = mid
				r = mid - 1
			else:
				l = mid + 1
		return res


class Solution:

	def splitArray(self, arr, N, K):
		l = 0
		h = 0
		for i in arr:
			l = max(l, i)
			h += i

		def ispossible(arr, maxsum, k):
			cnt = 0
			currsum = 0
			for i in arr:
				if currsum + i > maxsum:
					cnt += 1
					currsum = i
				else:
					currsum += i
			if currsum <= maxsum:
				cnt += 1
			return cnt <= k
		while l <= h:
			mid = l + (h - l) // 2
			if ispossible(arr, mid, K):
				ans = mid
				h = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def splitArray(self, arr, n, k):

		def cansplit(m):
			nonlocal k, arr
			s = 0
			cnt = 1
			for e in arr:
				s += e
				if s > m:
					cnt += 1
					s = e
			return cnt <= k
		(lo, hi) = (max(arr), sum(arr) + 1)
		while lo < hi:
			mi = lo + (hi - lo) // 2
			if cansplit(mi):
				hi = mi
			else:
				lo = mi + 1
		return lo