13
Jan
2020

Hackerrank Drawing Book (C++)

C++ :

 int pageCount(int n, int p) {
    /*
     * Write your code here.
     */
    int noOfPagesToTurn = 0, temp = 0;

    //starting from the beginning
    if(p == 1 || p == n || (p % 2 == 0 && n - p == 1)){
        noOfPagesToTurn = 0;
    }else{
        int startingPage = 2;
        noOfPagesToTurn = 0;
        for(; startingPage < n; startingPage+=2){
            noOfPagesToTurn++;
            if(startingPage == p || (startingPage + 1) == p){
                break;
            }
        }
        //check if book's max page is odd or even
        if(n % 2 == 0){
            startingPage = n - 2;
        }else{
            startingPage = n - 3;
        }
        temp = 0;
        for(; startingPage > 1; startingPage-=2){
            temp++;
            if(startingPage == p || (startingPage + 1) == p){
                break;
            }
        }
        if(temp < noOfPagesToTurn){
            noOfPagesToTurn = temp;
        }
    }

    return noOfPagesToTurn;
}

Explanation:

Set both noOfPagesToTurn and temp variables to 0. The first if checks if the page to turn to is 1, the last page n, or if the book has odd no. of pages and the page to turn to is n – 1 (If book has say, 7 pages, and page to turn to if 6, page 6 is just beside page 7, so no need to turn further.), if page p meets any of the condition above, additional flips required if 0, so 0 is returned.

Otherwise, starting from the next page after the beginning of the book, set the starting page to 2. For each +2 pages, check if the page p has been flipped to, by checking the number with starting page or the page adjacent to it. The total number of flips needed from the beginning of the book is recorded in noOfPagesToTurn. Basically, this checks the page number on the left side of the book.

Next, starting from the back of the book, check if the max page number n is odd or even. If it’s odd, start 3 pages before the last page, otherwise, start 2 pages. Similarly, this checks the page number on the left side of the book, only this time starting from the back. Each flip is recorded in temp.

At the end, check if flipping from the front or the back or the back of the book requires more flips. Assign the lowest number possible to noOfPagesToFlip and return it.

While checking test cases for the problem, another possible solution came up. This solution is to split the total number of pages into 2 (find average number of pages), and check if the page to flip to is nearer to the back or front of the book. Flip from the back or front as needed. Perhaps I’ll implement this in another language when we do another run though of algorithm practice.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *