Geek is organizing a birthday party, so his friends brought a cake for him. The cake consists of N chunks, whose individual sweetness is represented by the sweetness array. Now at the time of distribution, Geek cuts the cake into K + 1 pieces to distribute among his K friends. One piece he took for himself. Each piece consists of some consecutive chunks. He is very kind, so he left the piece with minimum sweetness for him.
You need to find the maximum sweetness that the Geek can get if he distributes the cake optimally.
Example 1:
Input:
N  = 6, K = 2
sweetness[] = {6, 3, 2, 8, 7, 5}
Output:
9
Explanation:
Geek can divide the cake to [6, 3], [2, 8], [7, 5] 
with sweetness level 9, 10 and 12 respectively.
Example 2:
Input:
N  = 7, K = 3
sweetness[] = {1, 2, 4, 7, 3, 6, 9}
Output:
7
Explanation:
Geek can divide the cake to [1, 2, 4], [7], [3, 6], [9] 
with sweetness level 7, 7, 9 and 9 respectively.
Your Task:
You need to complete the maxSweetness() function which takes an integer array of sweetness, an integer N and an integer K as the input parameters and returns an integer denoting the maximum sweetness that the Geek can get.
Expected Time Complexity: O(NlogM), where M is the sum of elements in the array.
Expected Space Complexity: O(1)
Constraints:
1 <= N <= 10^{5}
0 <= K < N
1 <= sweetness[i] <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution():

    def maxSweetness(self, sweetness, n, k):

        #your code goes here

Solutions:
class Solution:

	def Solve(self, mid, arr, k):
		sum = 0
		person = 0
		for i in range(len(arr)):
			sum += arr[i]
			if sum >= mid:
				person += 1
				sum = 0
		return person >= k + 1

	def maxSweetness(self, sweetness, n, k):
		low = min(sweetness)
		high = sum(sweetness)
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			if self.Solve(mid, sweetness, k):
				ans = mid
				low = mid + 1
			else:
				high = mid - 1
		return ans


class Solution:

	def maxSweetness(self, sweetness, n, k):
		(left, right) = (min(sweetness), sum(sweetness) // (k + 1))
		while left < right:
			mid = (left + right + 1) // 2
			(count, curr_sum) = (0, 0)
			for s in sweetness:
				curr_sum += s
				if curr_sum >= mid:
					count += 1
					curr_sum = 0
			if count >= k + 1:
				left = mid
			else:
				right = mid - 1
		return left


class Solution:

	def maxSweetness(self, sweetness, n, k):
		left = 1
		right = sum(sweetness)
		while left < right:
			mid = (left + right + 1) // 2
			cuts = 0
			cur_sweetness = 0
			for s in sweetness:
				cur_sweetness += s
				if cur_sweetness >= mid:
					cuts += 1
					cur_sweetness = 0
			if cuts >= k + 1:
				left = mid
			else:
				right = mid - 1
		return left


class Solution:

	def maxSweetness(self, sweetness, n, K):
		(l, r) = (0, sum(sweetness))
		while l < r:
			mid = (l + r + 1) // 2
			(count, cur_sum) = (0, 0)
			for s in sweetness:
				cur_sum += s
				if cur_sum >= mid:
					cur_sum = 0
					count += 1
			if count >= K + 1:
				l = mid
			else:
				r = mid - 1
		return l


class Solution:

	def maxSweetness(self, sweetness, N, K):
		left = 1
		right = sum(sweetness)
		while left < right:
			mid = (left + right + 1) // 2
			pieces = 0
			current_sweetness = 0
			for s in sweetness:
				current_sweetness += s
				if current_sweetness >= mid:
					pieces += 1
					current_sweetness = 0
			if pieces >= K + 1:
				left = mid
			else:
				right = mid - 1
		return left


class Solution:

	def maxSweetness(self, sweetness, n, k):
		lb = min(sweetness)
		ub = sum(sweetness)

		def slices(candidate):
			(current, number_of_slices) = (0, 0)
			for i in range(len(sweetness)):
				current += sweetness[i]
				if current >= candidate:
					number_of_slices += 1
					current = 0
			return number_of_slices
		while lb + 1 < ub:
			mid = (lb + ub) // 2
			n_slices = slices(mid)
			if n_slices >= k + 1:
				lb = mid
			else:
				ub = mid
		if slices(ub) == k + 1:
			return ub
		return lb


class Solution:

	def maxSweetness(self, sweetness, n, k):

		def isPossible(sw, k, mid):
			count = 0
			summ = 0
			for x in sw:
				summ += x
				if summ >= mid:
					count += 1
					summ = 0
			return count >= k + 1
		high = sum(sweetness)
		low = min(sweetness)
		mid = 0
		while low <= high:
			mid = (low + high) // 2
			if isPossible(sweetness, k, mid):
				low = mid + 1
			else:
				high = mid - 1
		return low - 1


class Solution:

	def solve(self, val, arr, k):
		n = len(arr)
		sumo = 0
		for i in range(n):
			if sumo >= val:
				sumo = 0
				k -= 1
			sumo += arr[i]
		if sumo >= val:
			k -= 1
		if k > -1:
			return False
		return True

	def maxSweetness(self, sweetness, n, k):
		l = 0
		r = sum(sweetness)
		while l < r - 1:
			mid = (l + r) // 2
			if self.solve(mid, sweetness, k):
				l = mid
			else:
				r = mid - 1
		while r:
			if self.solve(r, sweetness, k):
				return r
			r -= 1


class Solution:

	def maxSweetness(self, sw, n, k):
		l = 1
		r = 10 ** 9
		ans = 0
		while l <= r:
			m = (l + r) // 2
			p = 0
			cur = 0
			for i in range(0, n):
				cur += sw[i]
				if cur >= m:
					p += 1
					cur = 0
			if p >= k + 1:
				ans = m
				l = m + 1
			else:
				r = m - 1
		return ans


class Solution:

	def maxSweetness(self, sweetness, N, K):
		low = 0
		high = sum(sweetness)
		while low < high:
			mid = (low + high + 1) // 2
			num_pieces = 0
			curr_sweetness = 0
			for s in sweetness:
				curr_sweetness += s
				if curr_sweetness >= mid:
					num_pieces += 1
					curr_sweetness = 0
			if num_pieces >= K + 1:
				low = mid
			else:
				high = mid - 1
		return low


class Solution:

	def maxSweetness(self, sweetness, n, k):
		l = 0
		h = sum(sweetness)
		while l <= h:
			mid = (l + h) // 2
			(piece, sweet) = (0, 0)
			for x in sweetness:
				sweet += x
				if sweet >= mid:
					piece += 1
					sweet = 0
			if piece < k + 1:
				h = mid - 1
			else:
				l = mid + 1
		return h


class Solution:

	def maxSweetness(self, sweetness, n, k):

		def giveans(val):
			s = 0
			count = 0
			ans = float('inf')
			for i in sweetness:
				s += i
				if s > val:
					s = 0
					count += 1
			if count < k + 1:
				return 1
			return 0
		l = 1
		h = sum(sweetness)
		res = 0
		while l <= h:
			m = (l + h) // 2
			if giveans(m):
				res = m
				h = m - 1
			else:
				l = m + 1
		return res


class Solution:

	def maxSweetness(self, sweetness, n, k):
		l = 1
		h = 0
		for i in sweetness:
			h += i
		while l <= h:
			mid = l + (h - l) // 2
			p = 0
			s = 0
			for i in sweetness:
				s += i
				if s >= mid:
					p += 1
					s = 0
			if p < k + 1:
				h = mid - 1
			else:
				l = mid + 1
		return h


class Solution:

	def can_provide(self, this_much, arr, k):
		person = total = 0
		for i in arr:
			total += i
			if total >= this_much:
				person += 1
				total = 0
		return person >= k + 1

	def maxSweetness(self, sweetness, n, k):
		low = min(sweetness)
		high = sum(sweetness)
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			if self.can_provide(mid, sweetness, k):
				ans = mid
				low = mid + 1
			else:
				high = mid - 1
		return ans


class Solution:

	def maxSweetness(self, sweetness, n, K):
		total_sweetness = sum(sweetness)
		low = 1
		high = total_sweetness
		while low < high:
			mid = (low + high + 1) // 2
			pieces = 0
			current_sweetness = 0
			for s in sweetness:
				current_sweetness += s
				if current_sweetness >= mid:
					pieces += 1
					current_sweetness = 0
					if pieces == K + 1:
						break
			if pieces >= K + 1:
				low = mid
			else:
				high = mid - 1
		return high


class Solution:

	def maxSweetness(self, sweetness, n, k):
		start = min(sweetness)
		end = sum(sweetness)
		while start < end - 1:
			mid = (start + end) // 2
			r = self.get(sweetness, mid, k)
			if r:
				end = mid - 1
			else:
				start = mid
		if not self.get(sweetness, end, k):
			return end
		return start

	def get(self, arr, mid, k):
		count = 0
		s = 0
		for item in arr:
			if s + item >= mid:
				s = 0
				count += 1
			else:
				s += item
		if count >= k + 1:
			return False
		return True


class Solution:

	def maxSweetness(self, sw, n, k):

		def check(mid):
			peices = cur = 0
			for i in sw:
				cur += i
				if cur >= mid:
					cur = 0
					peices += 1
			return peices > k
		l = 0
		h = sum(sw)
		res = -1
		while l < h:
			mid = (l + h) // 2
			if check(mid):
				l = mid + 1
				res = mid
			else:
				h = mid - 1
		return res + 1 if check(res + 1) else res


class Solution:

	def maxSweetness(self, sweetness, n, k):

		def find(sweet, key, k):
			count = 0
			summ = 0
			for i in sweet:
				summ += i
				if summ >= key:
					summ = 0
					count += 1
			return count
		l = 0
		r = sum(sweetness)
		while l <= r:
			mid = (l + r) // 2
			check = find(sweetness, mid, k)
			if check < k + 1:
				r = mid - 1
			else:
				l = mid + 1
		return r


class Solution:

	def maxSweetness(self, sweetness, n, k):
		l = 0
		a = sweetness
		if k == 0:
			return sum(a)
		r = sum(a)
		res = -1
		while r >= l:
			m = (l + r) // 2
			ct = 1
			ans = 0
			ans1 = 10 ** 18
			for i in range(n):
				if ct > k:
					ans += a[i]
					continue
				if ans >= m:
					ans1 = min(ans1, ans)
					ans = a[i]
					ct += 1
				else:
					ans += a[i]
			if ct > k + 1 or (ct > k and ans >= m):
				ans1 = min(ans1, ans)
				res = ans1
				l = m + 1
			else:
				r = m - 1
		return res


class Solution:

	def canProvide(self, mid, sweetness, k):
		curr_total = 0
		person = 0
		for i in range(0, len(sweetness)):
			curr_total += sweetness[i]
			if curr_total >= mid:
				person += 1
				curr_total = 0
		return person >= k + 1

	def maxSweetness(self, sweetness, n, k):
		low = float('inf')
		high = 0
		for i in range(0, n):
			low = min(low, sweetness[i])
			high += sweetness[i]
		ans = 0
		while low <= high:
			mid = low + (high - low) // 2
			if self.canProvide(mid, sweetness, k):
				low = mid + 1
				ans = mid
			else:
				high = mid - 1
		return ans


class Solution:

	def check(self, mid, arr, N, K):
		sum = 0
		count = 0
		for i in range(N):
			sum += arr[i]
			if sum >= mid:
				count += 1
				sum = 0
		return count >= K + 1

	def maxSweetness(self, sweetness, N, K):
		start = 1
		end = 100000000000000.0
		ans = -1
		while start <= end:
			mid = (start + end) // 2
			if self.check(mid, sweetness, N, K):
				ans = mid
				start = mid + 1
			else:
				end = mid - 1
		return int(ans)


class Solution:

	def maxSweetness(self, sweetness, n, k):

		def good(x, sweetness, k):
			n = len(sweetness)
			(s, cnt) = (0, 0)
			for i in range(0, n):
				s += sweetness[i]
				if s >= x:
					s = 0
					cnt += 1
			return cnt >= k + 1
		(low, high) = (0, 1000000000.0)
		ans = -1
		while low <= high:
			mid = (low + high) // 2
			if good(mid, sweetness, k):
				low = mid + 1
				ans = mid
			else:
				high = mid - 1
		return int(ans)


class Solution:

	def maxSweetness(self, sweetness, n, k):

		def ispossible(val):
			(cnt, cur_sum) = (0, 0)
			for el in sweetness:
				cur_sum += el
				if cur_sum > val:
					cnt += 1
					cur_sum = 0
			return cnt >= k + 1
		(l, h) = (min(sweetness), sum(sweetness))
		while l <= h:
			m = l + (h - l) // 2
			if ispossible(m):
				l = m + 1
			else:
				h = m - 1
		return l


class Solution:

	def maxSweetness(self, arr, n, k):
		left = 0
		ts = sum(arr)
		while left <= ts:
			mid = (left + ts) // 2
			(pie, swe) = (0, 0)
			for x in arr:
				swe += x
				if swe >= mid:
					pie += 1
					swe = 0
			if pie < k + 1:
				ts = mid - 1
			else:
				left = mid + 1
		return ts


class Solution:

	def maxSweetness(self, sweetness, n, k):
		left = 1
		right = sum(sweetness)
		while left < right:
			mid = (left + right + 1) // 2
			pieces = 0
			current_sweetness = 0
			for s in sweetness:
				current_sweetness += s
				if current_sweetness >= mid:
					pieces += 1
					current_sweetness = 0
			if pieces > k:
				left = mid
			else:
				right = mid - 1
		return left


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

class Solution:

	def maxSweetness(self, sweetness, n, k):
		(low, high) = (0, sum(sweetness))
		while low <= high:
			mid = (low + high) // 2
			if isPossible(sweetness, mid, n, k):
				high = mid - 1
			else:
				low = mid + 1
		return low


class Solution:

	def maxSweetness(self, sweetness, n, k):

		def t(v):
			s = 0
			c = 0
			for i in sweetness:
				s += i
				if s >= v:
					c += 1
					s = 0
			if c >= k + 1:
				return True
			else:
				return False
		l = min(sweetness)
		h = sum(sweetness) + 1
		while l < h:
			m = (l + h) // 2
			if t(m) == False:
				h = m
			else:
				l = m + 1
		return l - 1


class Solution:

	def maxSweetness(self, sweetness, n, k):
		(low, ans) = (0, 0)
		high = 1000000000000000.0
		while low <= high:
			mid = (low + high) // 2
			(curSum, pieces) = (0, 0)
			for i in sweetness:
				curSum = curSum + i
				if curSum >= mid:
					curSum = 0
					pieces = pieces + 1
			if pieces >= k + 1:
				ans = mid
				low = mid + 1
			else:
				high = mid - 1
		return int(ans)


class Solution:

	def maxSweetness(self, sweetness, n, k):

		def validSweetness(mid):
			total_pieces = 0
			curr_sweetness = 0
			for s in sweetness:
				curr_sweetness += s
				if curr_sweetness >= mid:
					total_pieces += 1
					curr_sweetness = 0
			return total_pieces >= k + 1
		left = min(sweetness)
		right = sum(sweetness)
		while left < right:
			mid = (left + right + 1) // 2
			if validSweetness(mid):
				left = mid
			else:
				right = mid - 1
		return left


class Solution:

	def maxSweetness(self, sweetness, n, k):

		def count_pieces(sweetness, target):
			count = pieces = 0
			for s in sweetness:
				count += s
				if count >= target:
					pieces += 1
					count = 0
			return pieces
		(left, right) = (1, sum(sweetness) // (k + 1))
		result = 0
		while left <= right:
			mid = left + (right - left) // 2
			if count_pieces(sweetness, mid) >= k + 1:
				result = mid
				left = mid + 1
			else:
				right = mid - 1
		return result


class Solution:

	def maxSweetness(self, sweetness, n, k):

		def torelable(val):
			sweet = 0
			count = 0
			for i in sweetness:
				sweet += i
				if sweet >= val:
					count += 1
					sweet = 0
			if count >= k + 1:
				return True
			else:
				return False
		low = min(sweetness)
		high = sum(sweetness) + 1
		while low < high:
			mid = (low + high) // 2
			if torelable(mid) == False:
				high = mid
			else:
				low = mid + 1
		return low - 1


class Solution:

	def maxSweetness(self, sweetness, n, k):

		def isPossible(sw, k, mid):
			cnt = 0
			sm = 0
			for x in sw:
				sm += x
				if sm >= mid:
					cnt += 1
					sm = 0
			return cnt >= k + 1
		h = sum(sweetness)
		l = min(sweetness)
		mid = 0
		while l <= h:
			mid = (l + h) // 2
			if isPossible(sweetness, k, mid):
				l = mid + 1
			else:
				h = mid - 1
		return l - 1


class Solution:

	def solve(self, v, target, k):
		fq = 0
		sm = 0
		n = len(v)
		for i in range(n):
			if sm >= target:
				fq += 1
				sm = 0
			sm += v[i]
		if sm >= target:
			fq += 1
		return fq >= k

	def maxSweetness(self, sweetness, N, K):
		left = 1
		right = int(1000000000.0)
		ans = 0
		while right >= left:
			mid = (left + right) // 2
			if self.solve(sweetness, mid, K + 1):
				ans = mid
				left = mid + 1
			else:
				right = mid - 1
		return ans


class Solution:

	def maxSweetness(self, sweetness, n, k):

		def isPossible(sw, k, mid):
			ct = 0
			mm = 0
			for x in sw:
				mm += x
				if mm >= mid:
					ct += 1
					mm = 0
			return ct >= k + 1
		hh = sum(sweetness)
		lw = min(sweetness)
		md = 0
		while lw <= hh:
			md = (lw + hh) // 2
			if isPossible(sweetness, k, md):
				lw = md + 1
			else:
				hh = md - 1
		return lw - 1


class Solution:

	def maxSweetness(self, sweetness, n, k):
		minimumSweetness = min(sweetness)
		maximumSweetness = sum(sweetness)
		low = minimumSweetness
		high = maximumSweetness
		result = -1
		while low <= high:
			mid = low + (high - low >> 1)
			if self.isChunksPossible(sweetness, mid, k):
				result = mid
				low = mid + 1
			else:
				high = mid - 1
		return result

	def isChunksPossible(self, sweetness, geeksBite, k):
		chunkSweetness = 0
		count = 0
		for i in range(0, len(sweetness)):
			chunkSweetness += sweetness[i]
			if chunkSweetness >= geeksBite:
				count += 1
				chunkSweetness = 0
		return count >= k + 1


class Solution:

	def maxSweetness(self, sweetness, n, k):

		def tolerable(val):
			sweet = 0
			count = 0
			for i in sweetness:
				sweet += i
				if sweet >= val:
					count += 1
					sweet = 0
			if count >= k + 1:
				return True
			else:
				return False
		lo = min(sweetness)
		hi = sum(sweetness) + 1
		while lo < hi:
			mid = (lo + hi) // 2
			if tolerable(mid) == False:
				hi = mid
			else:
				lo = mid + 1
		return lo - 1


class Solution:

	def maxSweetness(self, sweetness, n, k):
		left = min(sweetness)
		right = sum(sweetness)
		while left < right:
			mid = (left + right + 1) // 2
			curr_sum = 0
			cuts = 0
			for i in range(n):
				curr_sum += sweetness[i]
				if curr_sum >= mid:
					cuts += 1
					curr_sum = 0
			if cuts >= k + 1:
				left = mid
			else:
				right = mid - 1
		return left