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\$
1
  • \$\begingroup\$ Is there some requirement to make the implementation as fast and efficient as possible? If not then I would completely discount all the bitwise operator nonsense in the answers you have received so far. As a lead engineer, I would reject the bit-based answers below and much prefer your original code, as it is a lot more readable, which is the prime directive for the majority of code. \$\endgroup\$ – Software Engineer Dec 20 '20 at 7:59
3
\$\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\$
2
  • 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
2
\$\begingroup\$

Review

First and foremost, BigInteger should be used sparingly, in the absolute must need basis because any operation using BigInteger is CPU intensive and memory inefficient.

The provided size of the input could range from int, long to BigInteger, an initial check is mandatory and then as the size of the value being processed decreases, it would be a wise to change the datatype being used. These ideas outlines the core idea for the solution, then we can tweak more optimizations using binary operations.

Other improvement that can be made is to skip mod modular operations as it involves division and BigInteger division is hard on CPU and memory. As the solution already seems to be thinking on binary operations, to replace mod, we can check the rightmost bit to determine the number is divisible by two. For our purpose we can use BigInteger.getLowestSetBit() and Long.numberOfTrailingZeros().

Similarly, there is another operation to improve, check if a number is divisible by 3. We can use BigInteger.testBit() and we can also improve Long operation which is left for further research.

Solution

Please find below the optimized solution:

import java.math.BigInteger;

public class Solution {

    private final static BigInteger MAX_LONG = BigInteger.valueOf(Long.MAX_VALUE);

    public static int solution(String s) {
        BigInteger n = new BigInteger(s);
        int count = 0;

        while (n.compareTo(MAX_LONG) > 0) {

            int zeros = n.getLowestSetBit();

            if (zeros > 0) {          // Even!
                n = n.shiftRight(zeros);
                count += zeros;
            } else {                  // Odd
                if (n.testBit(1))        // At least 2 least significant one bits
                    n = n.add(BigInteger.ONE);
                else                     // Only 1 least significant one bit
                    n = n.subtract(BigInteger.ONE);
                count++;
            }
        }

        // Value now fits with a primitive long
        long lv = n.longValue();

        while (lv > 3) {
            int zeros = Long.numberOfTrailingZeros(lv);
            if (zeros > 0) {          // Even!
                lv >>= zeros;
                count += zeros;
            } else {                  // Odd
                if (lv % 4 == 1)        // Only 1 least significant one bit
                    lv--;              
                else
                    lv++;               // At least 2 least significant one bits
                count++;
            }
        }

        if (lv == 3)
            count += 2;
        if (lv == 2)
            count += 1;

        return count;
    }
}

For details/description on the solution: Follow-up: How can we optimizing Java BigInteger operations?

\$\endgroup\$
0
1
\$\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.