You have N books, each with Ai number of pages. M students need to be allocated contiguous books, with each student getting at least one book. Out of all the permutations, the goal is to find the permutation where the student with the most pages allocated to him gets the minimum number of pages, out of all possible permutations.
Note: Return -1 if a valid assignment is not possible, and allotment should be in contiguous order (see the explanation for better understanding).
 
Example 1:
Input:
N = 4
A[] = {12,34,67,90}
M = 2
Output:113
Explanation:Allocation can be done in 
following ways:
{12} and {34, 67, 90} Maximum Pages = 191
{12, 34} and {67, 90} Maximum Pages = 157
{12, 34, 67} and {90} Maximum Pages =113.
Therefore, the minimum of these cases is 113,
which is selected as the output.
Example 2:
Input:
N = 3
A[] = {15,17,20}
M = 2
Output:32
Explanation: Allocation is done as
{15,17} and {20}
Your Task:
You don't need to read input or print anything. Your task is to complete the function findPages() which takes 2 Integers N, and m and an array A[] of length N as input and returns the expected answer.
Expected Time Complexity: O(NlogN)
Expected Auxilliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= A [ i ] <= 10^{6}
1 <= M <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Divide and conquer

Complete search

Starter code: class Solution:

    

    #Function to find minimum number of pages.

    def findPages(self,A, N, M):

        #code here



Solutions:
class Solution:

	def possible(self, mid, N, A, M):
		allo = 1
		pages = 0
		for i in range(N):
			if A[i] > mid:
				return False
			if pages + A[i] > mid:
				allo += 1
				pages = A[i]
			else:
				pages += A[i]
		if allo > M:
			return False
		return True

	def findPages(self, A, N, M):
		if N < M:
			return -1
		low = min(A)
		high = sum(A)
		res = -1
		while low <= high:
			mid = (low + high) // 2
			if self.possible(mid, N, A, M):
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


import math

class Solution:

	def isVal(self, A, N, M, mid):
		stdCount = 1
		sumE = 0
		for i in range(N):
			sumE += A[i]
			if sumE > mid:
				stdCount += 1
				sumE = A[i]
			if stdCount > M:
				return False
		return True

	def findPages(self, A, N, M):
		if M > N:
			return -1
		res = -1
		allSum = sum(A)
		i = max(A)
		j = allSum
		while i <= j:
			mid = math.floor((i + j) / 2)
			if self.isVal(A, N, M, mid):
				res = mid
				j = mid - 1
			else:
				i = mid + 1
		return res


class Solution:

	def findPages(self, A, N, M):
		if M > N:
			return -1

		def findStudentsReq(pages: int):
			students = 0
			capacity = 0
			for inst in A:
				if capacity + inst > pages:
					students += 1
					capacity = inst
				else:
					capacity += inst
			if capacity != 0:
				students += 1
			return students
		start = max(A)
		end = sum(A)
		ans = -1
		while start <= end:
			mid = start + (end - start) // 2
			students = findStudentsReq(mid)
			if students <= M:
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
		return ans