0
\$\begingroup\$

Problem

Reduce the number to 1 in a minimal number of steps, following the rules:

  • If the number is even, divide it by 2.
  • Otherwise, increment or decrement it by 1.

Limit: s can be up to 309 digits long.

Solution

public static int solution(String s) {
    BigInteger n = new BigInteger(s);
    BigInteger one = BigInteger.ONE;
    BigInteger two = BigInteger.TWO;
    BigInteger four = new BigInteger("4");
    int count = 0;

    while (n.compareTo(one) == 1) {
        count++;

        if( n.and(one).intValue() == 0 )
            n = n.divide(two);
        else if ( n.intValue() == 3 || n.mod(four).intValue() == 1)
            n = n.subtract(one);
        else
            n = n.add(one);
    }

    return count;
}

Is there a better way to do things binary-operations-wise for this problem?

At the moment the choice I am making among these functions:

  • use n.byteValue() to compare with the integer,
  • or use function n.equals().

What more can we improve?


Follow-up question posted here

\$\endgroup\$
7
4
\$\begingroup\$

Division of the big integers is a very expensive operation. Even a division by 2 is linear in terms of its length: all bits must be shifted. The overall complexity is \$O(n \log{n})\$.

A natural desire is to not do arithmetics at all, but simulate it. Convert the bigint to byte array, and inspect bits, pretending that you perform arithmetics. In broad strokes, run the loop (starting with cursor = 0) until the number is exhausted:

if bit(cursor) == 0
    // simulate division
    increment counter
    advance cursor
else
    peek next_bit
    if next_bit == 0
        // simulate subtraction
        increment counter by 2
        advance cursor by 2
    else
        // simulate addition
        while next_bit == 1
            increment counter
            advance cursor
            peek next_bit
        advance cursor
        set bit at cursor to 1
        

This touches each bit just once, driving the complexity down to \$O(n)\$. Care must be taken to correctly terminate the loop.

\$\endgroup\$
7
  • \$\begingroup\$ Can you explain how theirs is O(n log n)? \$\endgroup\$ – Kelly Bundy Dec 16 '20 at 5:16
  • \$\begingroup\$ @KellyBundy As I said, each division is \$O(n)\$, and there are about \$O(\log{n})\$ of them. \$\endgroup\$ – vnp Dec 16 '20 at 5:18
  • \$\begingroup\$ Isn't each division O(log n)? \$\endgroup\$ – Kelly Bundy Dec 16 '20 at 5:19
  • \$\begingroup\$ @KellyBundy Perhaps me being sloppy. To quote myself in terms of its length : \$n\$ in this analysis is not the bigint value, but its length; the number of bits. \$\endgroup\$ – vnp Dec 16 '20 at 6:16
  • \$\begingroup\$ This provides another dimension to solve the problem but looks a bit complicated, may be because I have not worked with Bits. But thank you @vnp for the perspective. \$\endgroup\$ – Anit Shrestha Manandhar Dec 16 '20 at 10:52
3
\$\begingroup\$

Divide by 2

As implemented, the even-test and divide by two operations is very inefficient.

BigInteger provides a getLowestSetBit() function, which returns "the index of the rightmost (lowest-order) one bit"

So if n.getLowestSetBit() returns 12, you can evenly divide the value by 2 a total of twelve times, before the least significant bit is set. Instead of actually doing the division by 2 that many times, the shiftRight(int n) function should be used:

   while (n.compareTo(one) == 1) {

       int zeros = n.getLowestSetBit();
       if (zeros > 0) {
          n = n.shiftRight(zeros);
          count += zeros;
       } else {
          count++;
          if ( n.intValue() == 3 || n.mod(four).intValue() == 1)
             n = n.subtract(one);
          else
             n = n.add(one);
          }
       }

Mod-4

Using n.mod(four).intValue() == 1 to test whether the value should be incremented or decremented is also horribly inefficient. Java must actually compute the modulo-4 remainder of the entire number; expecting it to optimize n.mod(four).intValue() == 1 into the much faster n.and(three).intValue() == 1 is expecting a lot from the optimizer.

But even computing n.and(three) is too much work! We know n is larger than 1, and that bit #0 is set. If bit #1 is set, then n % 4 == 3; if bit #1 is not set, then n % 4 == 1. And BigInteger also provides the testBit(int n) function:

          if ( n.intValue() == 3 || !n.testBit(1))
             n = n.subtract(one);
          else
             n = n.add(one);
          }

Possible Bug

n.intValue() == 3

Since n can have over 300 digits, at any point in the process, the value of n can easily overflow an integer:

Consider the 33-bit value 0x100000003. The number is not 3, but the intValue() of the number is 3.

You probably want to explicitly test for value BigInteger(3). Since comparing the entire value may be slower than testing a single bit, you may want to reorder the test to check the bit first.

          if ( !n.testBit(1) || n.equals(three) )
             n = n.subtract(one);
          else
             n = n.add(one);
          }
\$\endgroup\$
9
  • \$\begingroup\$ Maybe n.bitCount() == 2 would be a fast "equals three" test? \$\endgroup\$ – superb rain Dec 16 '20 at 19:06
  • \$\begingroup\$ @superbrain Hardly. Counting number of bits different from the sign bit is not likely a fast operation. Besides, it is wrong: new BigInteger("5").bitCount() == 2. \$\endgroup\$ – AJNeufeld Dec 16 '20 at 19:48
  • \$\begingroup\$ Oops, I meant bitLength. \$\endgroup\$ – superb rain Dec 16 '20 at 19:52
  • \$\begingroup\$ @superbrain It may take many cycles to calculate n.bitLength() when you have a 300-digit value. Equality comparison usually short-circuits at the first inequality, so is likely faster. I'll admit, I haven't profiled -- I'm just guessing. n.bitLength() == 2 is true for 2, 3, -3 and -4, so that test is not an obvious "equal to 3" test, despite the problem (probably) restricting the input numbers to positive values, and the previous even-odd test indicating we are on the odd path. \$\endgroup\$ – AJNeufeld Dec 16 '20 at 20:07
  • \$\begingroup\$ Surely it has the bit length already stored and wouldn't go and calculate it? \$\endgroup\$ – superb rain Dec 16 '20 at 20:08
3
\$\begingroup\$

You wrote:

    while (n.compareTo(one) == 1) {

As the documentation says:

This method is provided in preference to individual methods for each of the six boolean comparison operators (<, ==, >, >=, !=, <=). The suggested idiom for performing these comparisons is: (x.compareTo(y) <op> 0), where <op> is one of the six comparison operators.

So that would be:

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

I also find that much easier to understand. You just need to read the three parts n, one and > and mentally move the > between the operands, i.e., n > one.

\$\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.