# Google Foobar level 3

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 {
}
}
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.

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 {
}
}
counter++;
}
return counter;
}

• Never even heard of bitwise operators before this. Reading up on them now – Moe007 Aug 8 '18 at 13:41
• 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. – pattpass Aug 8 '18 at 14:02

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.