Minimum number of pages to read

Tags: , ,

Minimum number of pages to read

In previous post Ceiling in sorted array using binary search , we understood a very important concept about application of binary search in problems where minimum or maximum of something is asked. In the post mentioned above, we were asked to find minimum element which is greater than target value. We will use the same concept to solve another interesting problem : Find minimum number of pages to read for each student. Problem statement:
Given N different books and M students. Each book has certain pages. Every student is assigned to read some consecutive books.  Find a minimum number of pages each student has to read, so that all books are read. It should be noted that a student cannot read partial book, he/she needs to read entire book. For example, if number of pages of 8 books are as given below and there are 3 students to finish those books, a student has to read at least 84 pages. Books have to be read in sequence and either complete book is read or not read at all by student.

minimum number of pages to read

Books read by each student is shown below

If we change the order of books as shown below, minimum number of pages each student has to read are 82

Minimum number of pages to read : Thought process

Before we solve it, let’s revisit the basic premise to use binary search algorithm.

Binary search can be used if and only if for all x in candidate Set S, predicate(x) implies predicate(y) for all y > x.

In this problem, if students can finish N books with each student reading K pages, then it is definitely possible to finish N books by reading K+1 and more pages. This statement implies, that problem satisfy to apply binary search.

For binary search algorithm, three things are required : search space or candidate solution set, lower bound and upper bound of search space.
Assume that there is only one student, what will be the minimum number of pages he or she has to read to finish all books? Obviously, student has to read at least all pages in all books. This gives us upper bound of our solution set. Answer of this problem cannot be more than this upper bound.

Now, assume that we have N students but there is no book to read. Then minimum number of pages to be read by each student is zero. Well, student cannot read less than zero pages, hence lower bound of solution is zero.
At this point, we know lower and upper bound of solution. How can we find the required minimum number of page with N books and M students?

Idea is to start with middle of lower and upper bounds of pages to be read. Let’s call it K. With each student reading K pages, will all books be completed? If yes, it is always possible to finish all books with each student reading more than K pages, hence, there is no need to check from K to upper bound. All we need to verify that if there is a solution with each student reading K or less than K pages each.

Designing predicate function

What will be predicate? Predicate will be implemented by going through each book’s pages and see when sum of pages goes more than current candidate minimum. As soon it current sum goes more than candidate minimum, we add one more student. When all books are finished, we check if we required less than equal to M students. If yes, this candidate solution is valid and predicate should return true. If more than M students are required to finish all books, then current candidate is not valid and hence function return false.

Based on what is returned from predicate function, either right or left subset of candidate solution is discarded. In this example, if predicate function returns true, upper bound to be searched will be set to K. Else lower bound will be set to K+1.

Minimum number of pages to read  implementation

package com.company;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by sangar on 28.3.18.
 */
public class Books {
    public static boolean predicate(long[] books, long candidate, int days){

        long currentPages = 0;
        int studentRequired = 1;
        int i = 0;

        while(i<books.length){
            if(books[i] > candidate){
                return false;
            }
            if(currentPages + books[i] <= candidate){
                currentPages+=books[i];
                i++;
            }else{
                currentPages = 0;
                studentRequired++;
            }
        }
        return days >= studentRequired;
    }

    public static void main(String args[] ) throws Exception {
        Scanner scanner = new Scanner(System.in);

        int books = scanner.nextInt();
        int students = scanner.nextInt();

        long [] pages = new long[books];

        for(int i=0; i<books; i++){
            pages[i] = scanner.nextLong();
        }

        long low = 0;
        long high = Arrays.stream(pages).sum();

        while(low < high){
            long mid  = low + ( (high - low) >> 1);

            if(predicate(pages, mid, students)){
                high = mid;
            }else{
                low = mid+1;
            }
        }
        System.out.println(low);
    }
}

Complexity of algorithm to find minimum number of pages will be O(sum of pages of all books).

More problems on similar lines

It’s very interesting to see how many problems can be solved using same approach. I solved one on Hacker Rank : BooBoo and upsolving

  public static boolean predicate(long[] time, long candidateTime, int days){

        long currentTime = 0;
        int daysRequired = 1;
        int i = 0;

        while(i<time.length){
            if(time[i] > candidateTime){
                return false;
            }
            if(currentTime + time[i] <= candidateTime){
                currentTime+=time[i];
                i++;
            }else{
                currentTime = 0;
                daysRequired++;
            }
        }
        return days >= daysRequired;
    }

    public static void main(String args[] ) throws Exception {
        Scanner scanner = new Scanner(System.in);

        int tasks = scanner.nextInt();
        int days = scanner.nextInt();

        long [] time = new long[tasks];

        for(int i=0; i<tasks; i++){
            time[i] = scanner.nextLong();
        }

        /* What will be the maximum time he has to practice?
        It will be when he has only one day and all problems needs to be solved.
        that will give us the upper bound of time.

        What will be minimum time required? When he has no problems to be solved.
        That will give us lower bound of time.

        Idea is to start with middle of lower and upper bounds.And see if all problems can be solved
        by practicing that amount of time each day. If yes, there is a possibility that it can be done
        in less than that, hence, we try to find reduce our search space from lower bound to mid. Should mid be included?

        If all problems can not be solved by practicing mid amount of time, then there is no way it can be done
        by practicing less. Hence we increase the time and start looking in mid+1 to higher bound
        */

        //first let's set lower and higher bound.
        long low = 0;
        long high = Arrays.stream(time).sum();

        while(low < high){
            long mid  = low + ( (high - low) >> 1);

            if(predicate(time, mid, days)){
                high = mid;
            }else{
                low = mid+1;
            }
        }

        System.out.println(low);
    }

Similar method can be applied to topcoder problem Fair Work, try it yourself, if are able to solve it, please drop code in comment.

Please share if there is something is wrong or missing. If you want to contribute to website and share your knowledge with learners, please write to communications@algorithmsandme.com.