Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Allocate Books

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
680 upvotes
Asked in companies
GoogleArcesiumJP Morgan

Problem statement

Ayush is studying for ninjatest which will be held after 'N' days, And to score good marks he has to study 'M' chapters and the ith chapter requires TIME[i] seconds to study. The day in Ayush’s world has 100^100 seconds. There are some rules that are followed by Ayush while studying.

1. He reads the chapter in a sequential order, i.e. he studies i+1th chapter only after he studies ith chapter.

2. If he starts some chapter on a particular day he completes it that day itself.

3. He wants to distribute his workload over 'N' days, so he wants to minimize the maximum amount of time he studies in a day.

Your task is to find out the minimal value of the maximum amount of time for which Ayush studies in a day, in order to complete all the 'M' chapters in no more than 'N' days.

For example

if Ayush want to study 6 chapters in 3 days and the time that each chapter requires is as follows:
Chapter 1 = 30
Chapter 2 = 20
Chapter 3 = 10
Chapter 4 = 40
Chapter 5 = 5
Chapter 6 = 45

Then he will study the chapters in the following order 

| day 1 : 1 , 2 | day 2 : 3 , 4 | day 3 : 5 , 6 |
Here we can see that he study chapters in sequential order and the maximum time to study on a day is 50, which is the minimum possible in this case.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of the input contains a single positive integer 'T', denoting the number of test cases.

The first line of each test case contains two space-separated positive integers 'N' and 'M', denoting the number of days he can study before the ninja test and the number of chapters he has to study for the ninja test respectively.

The second line of each test case contains 'M' space-separated positive integers, where the ith integer denotes the time required to study the ith chapter.
Output Format:
For each test case print a single line containing a single integer denoting the maximum time Ayush studies in a day.

The output of each test case will be printed in a separate line.
Note:
You don't have to print anything, it has already been taken care of. Just Implement the given function.
Constraints:
1 <= T <= 10
1 <= N , M <= 10 ^ 4
1 <= TIME[i] <= 10 ^ 9 
It is considered that there are infinite seconds in a day, on the planet where Ayush lives.

Time limit: 1 sec.
Sample Input 1:
1
3 5
1 2 2 3 1
Sample Output 1:
4
Explanation of sample input 1:
The ayush will read the chapter as follows,
Day 1 : 1 , 2         Time required : 3
Day 2 : 3             Time required : 2
Day 3 : 4 , 5         Time required : 4
So the maximum time in a day is 4.
Sample Input 2:
1
4 7
2 2 3 3 4 4 1 
Sample Output 2:
6
Explanation of sample input 2:
The ayush will read the chapter as follows,
Day 1 : 1 , 2          Time required : 4
Day 2 : 3 , 4          Time required : 6
Day 3 : 5              Time required : 4
Day 4 : 6 , 7          Time required : 5
So the maximum time in a day is 6.
Hint

Can  we check all possible answers using brute force?

Approaches (2)
Brute force.
  • The answer could be between maximum of all available time  and the sum of the time required to study all chapters. So in this solution we have all the possible answers and let’s say we are at X so we want to find whether X can be the maximum time of a day Ayush studies or not.
  • We also want to allocate chapters sequentially so we will keep track of the chapters using currentChapter variable which would be initialized with 1 as we are on the first chapter at the beginning.
  • Now we will iterate through all the days and try to allocate as many chapters in a day as possible with the total time required to study them as less than or equal to X.
  • If we can cover all the chapters in N days using the above rule then we will say that it is possible for X to be the answer we will return X because it would also be the minimum possible
Time Complexity

O(K * M), where ‘K’ is the sum of the time required to read all the chapters and ‘M’ is the number of chapters.

 

Because for all the possible values of answer from 1 - K, we are iterating through all the chapters that are to be studied.

Space Complexity

O(1).

 

As we are just iterating over the chapter for every possible value of the answer and we are not storing anything so the space complexity will be O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Allocate Books
All tags
Sort by
Search icon

Interview problems

can someone pls help!!!!!!! why is the code not passing all the test cases?????

#include <bits/stdc++.h>

bool isPossible(vector<int> arr,int n,int m,int mid)

{

    long long timesum=0;

    long long daycount=1;

    for(int i=0;i<m;i++)

    {

        if(timesum+arr[i]<=mid)

        {

            timesum=timesum+arr[i];

        }

        else

        {

            daycount++;

            if(daycount>n||arr[i]>mid)

            {

                return false;

            }

            timesum=arr[i];

        }

    }   

    return true;

}

int binary( vector<int> arr,int n,int m)

{

    long long sum=0;

    for(int i=0;i<m;i++)

    {

        sum=sum+arr[i];

    }

    long long st=0,end=sum;

    long long  mid=st+(end-st)/2;

    long long ans=0;

    while(st<=end)

    {

        if(isPossible(arr,n,m,mid))

        {

             ans=mid;

             end=mid-1;

        }

        else

        {

            st=mid+1;

        }

        mid=st+(end-st)/2;

    }

    return ans;

}

long long ayushGivesNinjatest(int n, int m, vector<int> arr) 

{   

    // Write your code here.

    int c=binary(arr,n,m);

    return c;

}

14 views
0 replies
0 upvotes

Interview problems

Allocate Books Solution in java

import java.util.*;
import java.io.*;

public class Solution {
    public static long ayushGivesNinjatest(int n, int m, int[] time) {
        long low = 0;
        long high = 0;

        // Initialize low and high for binary search
        for (int t : time) {
            low = Math.max(low, t); // The maximum time for a single chapter
            high += t;               // The total time
        }

        // Function to check if we can partition with max time `mid`
        long result = high; // Start with the maximum possible time
        while (low <= high) {
            long mid = (low + high) / 2;
            if (canDistribute(time, n, mid)) {
                result = mid;  // mid is a valid option, try for a better (smaller) option
                high = mid - 1;
            } else {
                low = mid + 1; // mid is too small, increase it
            }
        }

        return result;
    }

    // Function to check if it's possible to distribute chapters in n days
    private static boolean canDistribute(int[] time, int n, long maxTime) {
        int days = 1;
        long currentDayTime = 0;

        for (int t : time) {
            if (currentDayTime + t > maxTime) {
                days++; // Start a new day
                currentDayTime = t; // Reset current day time
                if (days > n) { // If days exceed allowed days
                    return false;
                }
            } else {
                currentDayTime += t; // Add chapter time to the current day
            }
        }

        return true; // Successfully distributed within n days
    }

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt(); // Number of test cases
        while (t-- > 0) {
            int n = scanner.nextInt(); // Number of days
            int m = scanner.nextInt(); // Number of chapters
            int[] time = new int[m];
            for (int i = 0; i < m; i++) {
                time[i] = scanner.nextInt();
            }
            System.out.println(ayushGivesNinjatest(n, m, time));
        }
        scanner.close();
    }
}

java

10 views
0 replies
1 upvote

Interview problems

Binary Search method in Python

def countdays(time,mid):
    days = 1
    efforts = 0

    for i in time:
        if(efforts+i<=mid):
            efforts+=i
        else:
            days+=1
            efforts=i
    return days

def ayushGivesNinjatest(n, m, time):
    low = max(time)
    high = sum(time)

    while(low<=high):
        mid = (low+high)//2
        days = countdays(time,mid)
        if(days>n):
            low=mid+1
        else:
            high=mid-1
    return low

python

7 views
0 replies
0 upvotes

Interview problems

Minimizing Maximum Study Time Allocation Problem (Book Allocation Problem)

The problem revolves around dividing a set of tasks (in this case, study times) among a fixed number of days while minimizing the maximum time spent on any given day. The objective is to determine the least amount of maximum time a person must spend studying on the most burdensome day, ensuring that all tasks are completed within the given number of days.

 

Problem Statement:
  • You are given n days and m tasks, where each task requires a certain amount of time (represented as an array of integers time).

 

  • You need to allocate all tasks across n days such that the maximum amount of time spent on any one day is minimized.
  • The sum of tasks on any given day must not exceed a specific value, but the challenge is to find the minimum possible value of that maximum sum.

 

  • The task times must be allocated sequentially, meaning you cannot rearrange them.

 

Constraints:
  • If any task requires more time than the allowed maximum time for a day (mid), that configuration is considered invalid.

 

  • The solution must handle edge cases where the task distribution cannot be done within the given number of days.

 

#include <bits/stdc++.h>
using namespace std;

// Helper function to check if a given 'mid' value can be the answer
bool isPossible(int n, int m, long long int mid, vector<int>& time) {
    int days = 1;
    long long int efforts = 0;

    for (int i = 0; i < m; i++) {
        if (time[i] > mid) return false; // Single time value exceeds 'mid', so not possible

        if (efforts + time[i] <= mid) {
            efforts += time[i];
        } else {
            days++;
            if (days > n) return false; // More days needed than available
            efforts = time[i];
        }
    }
    return true;
}

// Recursive binary search function to find minimum possible maximum time
long long int MinValueOfMaxTime(int n, int m, long long int s, long long int e, vector<int>& time, long long int ans = 0LL) {
    // Base case: if start exceeds end, return the best answer found so far
    if (s > e) return ans;

    long long int mid = s + (e - s) / 2;

    if (isPossible(n, m, mid, time)) {
        // If mid is a valid answer, try finding a smaller maximum
        return MinValueOfMaxTime(n, m, s, mid - 1, time, mid);
    } else {
        // If mid is not valid, increase the minimum possible value
        return MinValueOfMaxTime(n, m, mid + 1, e, time, ans);
    }
}

long long ayushGivesNinjatest(int n, int m, vector<int> time) {    
    if (m == 0) return 0;
    if (n == 0) return -1;

    long long int s = *max_element(time.begin(), time.end());
    long long int e = accumulate(time.begin(), time.end(), 0LL);
    
    return MinValueOfMaxTime(n, m, s, e, time);
}
10 views
0 replies
0 upvotes

Interview problems

C++ Solution || Binary Search Approach || All Test Case Pass

#include <bits/stdc++.h>  

bool isPossibleAnswer(int n, int m, long long int mid, vector<int> time) {

 

  long long int studentCount = 1;

  long long int pageSum = 0;

 

  for (int i = 0; i < m; i++) {

    if (pageSum + time[i] <= mid) {

      pageSum += time[i];

    } else {

 

      studentCount++;

      if (studentCount > n || time[i] > mid) {

        return false;

      }

      pageSum = time[i];

    }

  }

  return true;

}

 

long long ayushGivesNinjatest(int n, int m, vector<int> time) {

  long long s = 0;

  long long sum = 0;

  for (int i = 0; i < m; i++) {

    sum += time[i];

  }

  long long e = sum;

  long long ans = -1;

  long long int mid = s + (e - s) / 2;

 

  while (s <= e) {

    if (isPossibleAnswer(n, m, mid, time)) {

      ans = mid;

      e = mid - 1;

    } else {

      s = mid + 1;

    }

    mid = s + (e - s) / 2;

  }

  return ans;

}

73 views
0 replies
1 upvote

Interview problems

C++ using binary search easy solution passes all test cases

#include <bits/stdc++.h>

bool Possible(int n, int m, long long int mid, vector<int> time){

long long int studentcount = 1;

long long int pagesum = 0;

 

for(int i=0; i<m; i++){

 

if(pagesum+time[i]<=mid){

    //first student ke liye kitne page allocate hue hai

  pagesum+=time[i];

}

else{

 

studentcount++;

// check next student ke liye page jyada to nahi hai

if(studentcount>n || time[i]>mid){

return false;

 

}

 

pagesum=time[i];

}

}

 

return true;

}

 

long long ayushGivesNinjatest(int n, int m, vector<int> time)

{

 

long long s = 0;

 

long long sum = 0;

 

for(int i=0; i<m; i++){

 

sum+=time[i];

 

}

 

long long e = sum;

 

long long ans = -1;

 

long long int mid = s + (e - s) / 2;

 

while(s <= e){

 

if (Possible(n, m, mid,time)) {

ans = mid;

 

e = mid - 1;

 

} else {

 

s = mid + 1;

 

}

 

mid = s + (e - s) / 2;

 

}

 

return ans;

 

}

43 views
0 replies
0 upvotes

Interview problems

why is the solution not passing all the test cases?

#include <bits/stdc++.h> 

bool ispossible(int mid,int m, vector<int> time,int n)

{int i=0,sum=0,count=0;

for(int i=0;i<m;i++)

{

    if((time[i]>mid)||(count==n))

    {return false;}

    sum=sum+time[i];

    if(sum==mid)

    {sum=0;

    count++;}

    if(sum>mid)

    {sum=0;

    count++;

    i=i-1;}

 

}

if(count>n)

{return false;}

else if(count<=n)

{return true;}

}

long long ayushGivesNinjatest(int n, int m, vector<int> time) 

{   int sum=0;

for(int i=0;i<m;i++)

    {sum=sum+time[i];}

    int start=0,mid,ans=-1,end;

    

    end=sum;

        while(start<=end)

    {

        mid=start+((end-start)/2);

        if(ispossible(mid,m,time,n))

        {end=mid-1;

        ans=mid;}

        else

        {start=mid+1;}

    }

    if(m<n)

     {ans=-1;}

    return ans;

}#include <bits/stdc++.h> 

bool ispossible(int mid,int m, vector<int> time,int n)

{int i=0,sum=0,count=0;

for(int i=0;i<m;i++)

{

    if((time[i]>mid)||(count==n))

    {return false;}

    sum=sum+time[i];

    if(sum==mid)

    {sum=0;

    count++;}

    if(sum>mid)

    {sum=0;

    count++;

    i=i-1;}

 

}

if(count>n)

{return false;}

else if(count<=n)

{return true;}

}

long long ayushGivesNinjatest(int n, int m, vector<int> time) 

{   int sum=0;

for(int i=0;i<m;i++)

    {sum=sum+time[i];}

    int start=0,mid,ans=-1,end;

    

    end=sum;

        while(start<=end)

    {

        mid=start+((end-start)/2);

        if(ispossible(mid,m,time,n))

        {end=mid-1;

        ans=mid;}

        else

        {start=mid+1;}

    }

    if(m<n)

     {ans=-1;}

    return ans;

}

30 views
0 replies
0 upvotes

Interview problems

JAVA SOLUTION || Allocate Books ||

import java.util.* ;

import java.io.*; 

public class Solution {

 

    static boolean isFeasible(int n , int m , int[] time , long mid ){

        int days = 1;

        long sum =0;

 

        for(int i=0;i<m;i++){

            if(sum + time[i] > mid){

                sum = time[i];

                days++;

            }else{

                sum += time[i];

            }

        }

 

        return days<=n;

    }

 

    static long maximum(int[] time){

        long min = time[0];

        for(int i=1;i<time.length;i++){

            min = Math.max(time[i], min);

        }

        return min;

    }

    public static long ayushGivesNinjatest(int n, int m, int[] time) {

        // Write your code here.

 

        long min = (long)maximum(time );

        long max = 0L;

        for(int i=0;i<m;i++){

            max += time[i];

        }

 

        long res = Integer.MAX_VALUE;

 

        while(min<=max){

            long mid = (min + max)/2;

            if(isFeasible(n,m, time , mid)){

                max = mid-1;   

                res =  mid;

            }else{

                min = mid+1;

            }

        }

 

        return res;

    }

}

6 views
0 replies
0 upvotes

Interview problems

Using Binary Search in C++

#include <bits/stdc++.h>

 

bool isPossibleAnswer(int n, int m, long long int mid, vector<int> time){

 

long long int countNum = 1;

long long int sum = 0;

 

for(int i=0; i<m; i++){

if(sum+time[i]<=mid){

sum+=time[i];

}

else{

countNum++;

if(countNum>n || time[i]>mid){

return false;

}

sum=time[i];

}

}

return true;

}

 

long long ayushGivesNinjatest(int n, int m, vector<int> time)

 

{

 

// Write your code here.

long long s = 0;

long long sum = 0;

 

for(int i=0; i<m; i++){

sum+=time[i];

 

}

 

long long e = sum;

long long ans = -1;

long long int mid = s + (e - s) / 2;

 

while(s <= e){

if (isPossibleAnswer(n, m, mid,time)) {

ans = mid;

e = mid - 1;

} else {

s = mid + 1;

}

mid = s + (e - s) / 2;

}

return ans;

}

128 views
1 reply
1 upvote

Interview problems

Using c++ ,Binary Search algorithm used

All test cases passed, learned from Babbar Sir.

86 views
0 replies
0 upvotes
Full screen
Console