2
\$\begingroup\$

Over the past few weeks, I've been doing the Google Foobar challenges and I've been progressing quite well. I'm currently 1/3 of the way through the third level. However, there were plenty of times over the past few weeks where I felt that my code could have been a lot better. So today I stumbled upon this community and I think that it will be a good idea to ask you guys to review my code.

So this is what I was instructed to do:

The fuel control mechanisms have three operations:

  1. Add one fuel pellet

  2. Remove one fuel pellet

  3. Divide the entire group of fuel pellets by 2 (due to the destructive energy released when a quantum antimatter pellet is cut in half, the safety controls will only allow this to happen if there is an even number of pellets)

Write a function called answer(n) which takes a positive integer as a string and returns the minimum number of operations needed to transform the number of pellets to 1. The fuel intake control panel can only display a number up to 309 digits long, so there won't ever be more pellets than you can express in that many digits.

This is my solution:

    public static int answer(String n) { 
        //convert n to BigInteger
        BigInteger x = new BigInteger(n);
        BigInteger two = new BigInteger("2");
        BigInteger three = new BigInteger("3");
        BigInteger y, z;
        int counter = 0;

        //Loop for as long as x is not equal to 1
        while(!x.equals(BigInteger.ONE)){
            //Check if x is divisible by 2
            if(x.mod(two).equals(BigInteger.ZERO)){
                //divide x by 2
                x = x.divide(two);
            } else {
                //subtract x by 1 and then divide by 2 store in variable z
                y = x.subtract(BigInteger.ONE);
                z = y.divide(two);
                //check if the result of that leaves a number that's divisible by 2, or check if x is equal to 3
                if(z.mod(two).equals(BigInteger.ZERO) || x.equals(three)){
                    x = y;
                } else {
                    x = x.add(BigInteger.ONE);    
                }
        }
        counter++;
    } 
    return counter;
}

For this challenge, I'm a lot more confident and happy with the cleanliness of my code compared to the previous challenges. But seeing that I'm still very much a newbie and this being my first time using BigInteger, I'd very much like a review.

\$\endgroup\$
2
\$\begingroup\$

You could have used the bitwise methods in BigInteger.

You could get rid of both .mod(two) and BigInteger two and instead use !__.testBit(0).

Returns true if and only if the designated bit is set. (Computes ((this & (1<<n)) != 0).)

You could have also used .shiftRight(1) to divide by 2

Returns a BigInteger whose value is (this >> n). Sign extension is performed. The shift distance, n, may be negative, in which case this method performs a left shift. (Computes floor(this / 2n).)

I haven't put a ton of thought, but I think you could also find a clever way to get rid of 3 with testBit and bitLength, but I think that .compareTo/equals method is alright.

public static int answer(String n) {
    //convert n to BigInteger
    BigInteger x = new BigInteger(n);
    BigInteger three = new BigInteger("3");
    BigInteger y, z;
    int counter = 0;

    //Loop for as long as x is not equal to 1
    while(!x.equals(BigInteger.ONE)){
        //Check if x is divisible by 2
        if(!x.testBit(0)){
            //divide x by 2
            x = x.shiftRight(1);
        } else {
            //subtract x by 1 and then divide by 2 store in variable z
            y = x.subtract(BigInteger.ONE);
            z = y.shiftRight(1);
            //check if the result of that leaves a number that's divisible by 2, or check if x is equal to 3
            if(!z.testBit(0) || x.equals(three)){
                x = y;
            } else {
                x = x.add(BigInteger.ONE);
            }
        }
        counter++;
    }
    return counter;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Never even heard of bitwise operators before this. Reading up on them now \$\endgroup\$ – Moe007 Aug 8 '18 at 13:41
  • \$\begingroup\$ Bitwise operators are available for numerical primitives in Java as well as BigInteger. They provide a bit of a performance benefit by leveraging the binary representation of numbers. Hackerrank has bit manipulation problems you can do to play around with these operators. Try to solve 2-3 easy problems to get introduced to them. Leetcode has a problem set as well, but they are pretty poor. Good luck on the fizzbuzz challenge. \$\endgroup\$ – pattpass Aug 8 '18 at 14:02
0
\$\begingroup\$

Taking up patpass' suggestion to use testBit for the check whether a number is even, I suggest to write a simple function isEven to check exactly that. This will make the code much clearer to read than some arbitrary math in an if-expression:

private static boolean isEven(BigInteger numberToTest) {
    return !numberToTest.testBit(0);
}

Regarding naming and scoping:

  • x, y, z, and n should be named more expressively, along the lines of numberOfFuelPellets, whatever, whatever, inputAsString. (The function name answer also is a no-go but that's in the assignment.)
  • y and z should be declared inside the else-part where you need them - keep the scope as small as possible.
  • two and three should be constants, i.e. static final class fields (and named TWO and THREE in that case) (if the challenge permits that)

... and I strongly advise against using right-shifts for division by 2. This kind of "clever optimization" mainly makes the code harder to understand. In some special cases there might be a runtime benefit from doing this, but only perform such tricks if you verified that you have a performance problem and introduced some serious benchmarks to prove that the performance promlem goes away by doing that.

\$\endgroup\$

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.