2
\$\begingroup\$

Here is a HackerRank challenge. Given a book with n pages (with 1 ≤ n ≤ 105), how many page turns are needed to arrive at page p, starting from either the front or the back? The book is laid out with page 1 on the right.

I have got following solution to the given problem.

import java.util.*;
public class Solution {

    static int solve(int n, int p){
        // Complete this function
        if(n==p)
            return 0;
        if(p%2==0){
            if(n-p==p)
                return (p-1)/2;
            else{
                if(n-p>p)
                    return p/2;
                else
                    return (n-p)/2;
            }
        }
        if(n%2==0 && p%2!=0){
            if(n-p==p)
                return (p-1)/2;
            else{
                if(n-p>p)
                    return p/2;
                else
                    return (n-p+2)/2;
                }
        }
        else

             if(n-p>p)
                    return p/2;
                else
                    return (n-p)/2;        

    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int p = in.nextInt();
        int result = solve(n, p);
        System.out.println(result);
    }
}

Although it is working code, I am not satisfied with it. It seems very messy. How can I reduce branch statements in my code, or otherwise improve it?

\$\endgroup\$
5
\$\begingroup\$

Math.min(p / 2, n / 2 - p / 2)

Explanation:

  • If we go from start page \$1\$ takes \$0\$; page \$2,3\$ takes \$1\$; page \$4,5\$ takes \$2\$ and so on. So for \$2k,2k+1\$ we require \$k\$ turns. Hence \$p=2k,2k+1\implies \lfloor p/2\rfloor = k\$
  • If we go from the back it depends on:

    • If \$n\$ is odd then \$n,n-1\$ take \$0\$; \$n-2,n-3\$ takes \$1\$ and so on. So \$n-2k,n-(2k+1)\$ takes \$k\$.

      Let \$n=2q+1\$ then \$p=2q-2k+1,2q-2k\implies \lfloor p/2\rfloor = q-k\$

      i.e. \$k=q-\lfloor p/2\rfloor=\lfloor n/2\rfloor -\lfloor p/2\rfloor \$

    • If \$n\$ is even then \$n\$ takes \$0\$; \$n-1,n-2\$ takes \$1\$ and so on. So \$n-(2k-1),n-2k\$ takes \$k\$.

      Let \$n=2q\$ then \$p=2q-2k,2q-2k+1\implies \lfloor p/2\rfloor=q-k\$

      i.e. \$k=q-\lfloor p/2\rfloor=\lfloor n/2\rfloor -\lfloor p/2\rfloor\$

\$\endgroup\$
  • \$\begingroup\$ This failed all the test cases on the site, though... \$\endgroup\$ – Quelklef Jul 28 '17 at 15:56
  • \$\begingroup\$ @Quelklef a typo (n-p) \$\endgroup\$ – RE60K Jul 28 '17 at 15:58
  • \$\begingroup\$ This is the solution I got as well (except instead of division it should be integer divison), but it fails the test case n=6 p=5 where the answer is 1 \$\endgroup\$ – Quelklef Jul 28 '17 at 15:59
  • \$\begingroup\$ @Quelklef n/2-p/2 works \$\endgroup\$ – RE60K Jul 28 '17 at 16:03
  • \$\begingroup\$ Yup, looks like you solved it, and in the best way possible. \$\endgroup\$ – Quelklef Jul 28 '17 at 16:06
4
\$\begingroup\$

I don't really understand your approach. There seems to be a much simpler way to do this.

int from_front = p / 2;

int from_back;
if (n % 2 == 0) from_back = (n - p + 1) / 2;
else from_back = (n - p) / 2;

return Math.min(from_front, from_back);
\$\endgroup\$
  • \$\begingroup\$ Actually I started with simpler code like yours but 1 test case made me to code like that. Thanks. :) \$\endgroup\$ – Rohith. Jul 28 '17 at 16:26
0
\$\begingroup\$

Thanks for sharing the code.

I don't like challenge sites like hacker rank because they focus on quick and dirty solutions but what we need are coders that focus on correctness and maintainability. So thank you for sowing that you care by posting your approach here.

Avoid single letter names

In Java the length of identifier names is virtually unlimited. There is no penalty in any way for long identifier names. So don't be stingy with letters when choosing names.

Try to replace n with targetPage and p with pageCount or similar.

reduce code duplication

One of the key features of clean code is that it is free of duplicated code. In your code you have this block at 2 places:

           if(n-p>p)
                return p/2;
            else
                return (n-p)/2;

And furthermore you have a similar block too:

            if(n-p>p)
                return p/2;
            else
                return (n-p+2)/2;
            }

Step one: convert similar code to identical code

The difference is that the "unique" block has an additional operation with a literal value. So we could introduce this operation to the other two places using the operations neutral element:

            if(n-p>p)
                return p/2;
            else
                return (n-p+0)/2;
            }

in order to make this code parts identical we have to convert the literal values to variables with the same name. In order to do so sou place the cursor on the 0 you just added and invoke the IDEs automated refactoring1 extract local variable (replace all occurences) and dont vorget to give a meaningful name:

    int backwardPageSkip = 0;
    if(n==p)
        return backwardPageSkip;
    if(p%2==backwardPageSkip){
        if(n-p==p)
            return (p-1)/2;
        else{
            if(n-p>p)
                return p/2;
            else
                return (n-p+backwardPageSkip)/2;
        }
    }
    if(n%2==backwardPageSkip && p%2!=backwardPageSkip){
        if(n-p==p)
            return (p-1)/2;
        else{
            if(n-p>p)
                return p/2;
            else
                return (n-p+2)/2;
            }
    }
    else

         if(n-p>p)
                return p/2;
            else
                return (n-p+backwardPageSkip)/2;  

In order to use this variable in the third location we need to assign the literal value to it right after entering the if:

    if(n%2==backwardPageSkip && p%2!=backwardPageSkip){
        backwardPageSkip=2;
        if(n-p==p)
            return (p-1)/2;
        else{
            if(n-p>p)
                return p/2;
            else
                return (n-p+backwardPageSkip)/2;
            }
    }

Step two: remove the code duplication

now we can select the 4 lines

            if(n-p>p)
                return p/2;
            else
                return (n-p+backwardPageSkip)/2;

and invoke the IDEs automated refactoring extract method. It should show that it found two more locations to change:
enter image description here

And this is the result including the renaming of n and p:

static int solve(int targetPage, int pageCount){
    // Complete this function
    int backwardPageSkip = 0;
    if(targetPage==pageCount)
        return backwardPageSkip;
    if(pageCount%2==backwardPageSkip){
        if(targetPage-pageCount==pageCount)
            return (pageCount-1)/2;
        else{
            return calculatePagesToTurn(targetPage, pageCount, backwardPageSkip);
        }
    }
    if(targetPage%2==backwardPageSkip && pageCount%2!=backwardPageSkip){
        backwardPageSkip=2;
        if(targetPage-pageCount==pageCount)
            return (pageCount-1)/2;
        else{
            return calculatePagesToTurn(targetPage, pageCount, backwardPageSkip);
            }
    } else
        return calculatePagesToTurn(targetPage, pageCount, backwardPageSkip);        

}
private static int calculatePagesToTurn(int targetPage, int pageCount, int backwardPageSkip) {
    if(targetPage-pageCount>pageCount)
        return pageCount/2;
    else
        return (targetPage-pageCount+backwardPageSkip)/2;
}

The next thing to do is to convert the 2 values of backwardPageSkip into constant as well as the other magic numbers you use throughout the program...

-------

@pinkfloydx33 Thanks for improving my answer.

Still a lot of extraneous else blocks. – pinkfloydx33

Yes. The technique I demonstrated can be applied multiple times. In this case there is still a duplication with this block:

        if(targetPage-pageCount==pageCount)
            return (pageCount-1)/2;
        else{
            return calculatePagesToTurn(targetPage, pageCount, backwardPageSkip);

This could (and should) be extractes to a separate method too...


Also the && p%2!=backwardPageSkip is redundant (always true due to first if statement) though it existed in the OP as well. – pinkfloydx33

Yes. The OP could have added an else to the preceding if instead, but that kind of logical improvements was not the subject of my answer...


I don't know Java but I believe this won't compile due to the double declaration of backwardPageSkip(where you assign it the value 2) – pinkfloydx33

You're right, fixed that to a simple re-assignment.


1 when refactoring your code avoid typing yourself and rely on the automated refactorings your IDE provides.

\$\endgroup\$
  • \$\begingroup\$ Still a lot of extraneous else blocks. Also the && p%2!=backwardPageSkip is redundant (always true due to first if statement) though it existed in the OP as well. I don't know Java but I believe this won't compile due to the double declaration of backwardPageSkip(where you assign it the value 2) \$\endgroup\$ – pinkfloydx33 Jul 28 '17 at 23:00
  • \$\begingroup\$ @pinkfloydx33 Thanks, updated the answer. \$\endgroup\$ – Timothy Truckle Jul 29 '17 at 7:21
  • \$\begingroup\$ My point about the else blocks was that if(x) { return a;} else { B;} can be cleaned up into if(x) {return a:} B; once you return inside the first branch of an if/else then the else becomes unnecessary and allows you to reduce nesting \$\endgroup\$ – pinkfloydx33 Jul 29 '17 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.