3
\$\begingroup\$

Over the past few weeks, I've been doing the Google Foobar challenges and I've been progressing quite well. I'm currently ⅓ 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\$ Dec 20, 2020 at 7:59

4 Answers 4

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, 2018 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, 2018 at 14:02
3
\$\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 problem goes away by doing that.

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

You can build on the code in Anit Shrestha's answer, adding a couple more optimizations to eliminate unnecessary loops (see comments):

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 minOperations = 0;
        int zeros;
        
        while(n.compareTo(MAX_LONG) == 1) { //n > MAX_LONG
            zeros = n.getLowestSetBit();    //Count how many low-significant zero bits there are
            if(zeros > 0) {              //n is even
                n = n.shiftRight(zeros); //n / (2*zeros)
                minOperations += zeros;
            } else if(n.testBit(1)) {       //At least two least significant bits set to 1
                n = n.add(BigInteger.ONE);  //All less significant ones become zeros
                
                /* We just added 1, so "n" is still greater than MAX_LONG, and we also know that 
                 * n is definitely even, so we can avoid executing the next cycle, it would be 
                 * useless as we already have all the information we need. */
                zeros = n.getLowestSetBit();
                n = n.shiftRight(zeros);
                minOperations += zeros + 1;
            } else {                 //n is odd and, the two least significant bits are "01"
                /* We know that the two least significant bits are "01", and to remove these bits,
                 * 3 operations are required: -1, /2 and /2, so potentially we can avoid running 
                 * another unnecessary loop. */
                n = n.shiftRight(2);
                minOperations += 3;  //3 operations: -1, /2 and /2 to remove the 2 least significant bits
            }
        }

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

        while (lv > 3) {
            zeros = Long.numberOfTrailingZeros(lv);
            if (zeros > 0) {
                lv >>= zeros;
                minOperations += zeros;
            } else if ((lv & 0x2) == 0x2) { //avoid using module which involves a division
                lv++;
                zeros = Long.numberOfTrailingZeros(lv);
                lv >>= zeros;
                minOperations += zeros + 1;         
            } else {
                lv >>= 2;
                minOperations += 3;
            }
        }
        /* We don't need to test n against 3 and 2, just do this: */
        minOperations += lv - 1; //3 -> 2; 2 -> 1; 1 -> 0; 0 -> -1

        return minOperations;
    }
}

Edit

This is another solution with a time complexity of O(1):

int solution(int n) {
    int count = 0;
    int plus1Operations = ((n >> 1) & n) | ((n >> 1) & ~n); //(Over)estimate how many "+1" operations are required
    plus1Operations &= ~(n + plus1Operations);              //Adjust the estimate

    if(plus1Operations > (n >> 2))  //If by mistake we used the "+1" operation with 3
        count = -1;                 //Start counting from -1

    //Do all operations "+1"; each remaining bit set to 1 in 'n' means a "-1" operation, except for the most-significant bit set to 1
    n += plus1Operations;

    count += Integer.bitCount(n | plus1Operations);               //Count all "+1" and "-1" operations
    count += Integer.SIZE - Integer.numberOfLeadingZeros(n) - 2;  //Count all "/2" operations
    
    return count;
}

The idea behind this solution is that we don't have to reduce n to 1 to find how many operations are needed to reduce n to 1; in other words, we don't have to show anyone the steps required to reduce to 1, what we really care about are:

  • How many "+1" operations are needed?
  • How many "-1" operations are needed?
  • How many "divided by 2" operations are needed?

To do this, I used some primitive binary operations to create the plus1Operations placeholder, where each bit set to 1 indicates a "+1" operation; after that, I did all the "+1" operations in one go (n += plus1Operations;), thus transforming n into a placeholder where each bit set to 1 indicates a "-1" operation.

And finally, the Hamming weight algorithm is used to count the bits set in n | plus1Operations, while to count the operations "divided by 2", just count how many bits there are to the right of the most significant bit set to 1 of n.

To handle numbers up to 309 digits, just transform this algorithm using the class BigInteger instead of int.

You can find the full explanation of this algorithm here:
https://github.com/parmi93/fuel-injection-perfection

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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