Integer division using recursion--and a few other interesting limitations

Question

I am trying to solve a puzzle in Java for my own edification. I am told there is a solution by the guy who designed the puzzle, but I'm not able to find it myself.

Here's the puzzle:

Implement the following method in Java

/**
 * Divides a natural number by two.
 * 
 * @param n
 *            The number to be divided
 * @updates n
 * @ensures n = floor(n/2)
 */
private static void split(NaturalNumber n) {...}

The NaturalNumber class is simply a class that stores a natural number using a string. ( That is, it can store numbers much larger than Integer.MAX_VALUE. )

The class provides these instance methods and inherited methods, as well as the NaturalNumber.isZero() method, which returns true if the instance's internal string value is "0", false otherwise.

It's worth noting that the NaturalNumber.divideBy10() method essentially pops the rightmost digit off the number, returns it as an int and updates the instance's internal value.

Do not use static properties on the main class to store values. Similarly, do not write static helper methods.

Do not convert n to some other data type and operate on that. Do not use external libraries.

Furthermore, split() must be implemented using recursion.

I have the following near solution worked out:

private static void split(NaturalNumber n) {
  // Initialize local variables.
  String stringBuffer = "";
  int numerator = 0;
  int quotient = 0;
  int remainder = 0;

  int thisDigit = n.divideBy10();

  if (n.isZero()) {
    quotient = thisDigit / 2;
    remainder = thisDigit % 2;
    n.transferFrom(new NaturalNumber2(quotient * 10 + remainder));
  } else {
    split(n);
    numerator = n.divideBy10() * 10 + thisDigit;
    quotient = numerator / 2;
    remainder = numerator % 2;
    if (!n.isZero()) {
      stringBuffer += n.toString();
    }
    stringBuffer += Integer.toString(quotient * 10 + remainder);
    n.transferFrom(new NaturalNumber2(stringBuffer));
  }
}

The above simply performs long division. But the last frame in the call stack needlessly appends the remainder of its operation onto the end of the solution.

I have seen solutions to similar problems that recursively subtract two from n, counting how many times two must be subtracted for n to become zero. But those solutions rely on the method having a return value; this puzzle requires there be no return value.

I can also see how to solve the puzzle using one function call to split() and internal loops. But I am told the solution must not rely on loops to operate on n.

Does anyone out there have any insight into a solution?

Answer 1

Suppose the digits of n are a...yz. If y is even, then the digits of n / 2 are the concatenation of a...y / 2 and z / 2. If y is odd, let Y = y - 1. Then the digits of n / 2 are the concatenation of a...Y / 2 and 1z / 2.

We can implement this as follows:

private static void split(NaturalNumber n) {
    int z = n.divideBy10();
    int y = n.divideBy10();

    if (n.isZero()) {
        // Base case.
        int result = (y * 10 + z) / 2;
        n.multiplyBy10(result / 10);
        n.multiplyBy10(result % 10);
    } else if (y % 2 == 0) {
        n.multiplyBy10(y);
        split(n);
        n.multiplyBy10(z / 2);
    } else {
        n.multiplyBy10(y - 1);
        split(n);
        n.multiplyBy10((10 + z) / 2);
    }
}

Incidentally, these method names are awful, and making NaturalNumbers mutable is a weird design choice.