Array of Products

A friend is interviewing for a job and sent me this problem:

Implement a Java method that accepts an array of integers (the array can be any arbitrary size) and replaces each integer in the parameter array with the product of all the other integers in the array. For example, if the parameter array was {1,2,3,4} then when the method returns the array should be {24,12,8,6} because 24=2*3*4, 12=1*3*4, 8=1*2*4, and 6=1*2*3. Provide your solution as a single .java file written in your usual style. The code should be production-quality and be ready for use in a live application.

I'm not applying for the job, but it looked interesting. In a moment an easy answer jumped out at me- multiply all the numbers together into one product, then for each number,
array[n] = (product/array[n])

And you have to count the zeroes, to handle the 2 special cases when there's one zero, or more. When you encounter a zero, count it, don't multiply it into the total, and note it's position. At the end, if the count of zero's is 1, set all the products to zero except put the accumulated product into the remembered position. If the count of zeroes is 2 or more, set all products to zero.
Probably you'll want to use Java's BigInteger types.

Without doing divisions

When I was young, divisions were expensive. So how would I do it avoiding divisions? In two ways.

1- a 2-pass solution that uses an extra buffer. Moving to the right, write into the buffer[n] the product of all numbers to the left of it. Then iterate from the right, computing the product to the right of each number. After the right product is computed for a slot, read the number in the slot put the right product times the left into the slot, and then multiply the number into the right product to pass on to the next.

2- If we multiply all n-1 integers together, we'd have to do that n times, and perform about n² multiplications. If I multiply together all but the last two, say a and b, into a product p, I could write down p*b and p*a and save n. If I multiply half of them together, I could use that product on the other half, and save n²/4 division. This shows the way to an O(n lg(n)) recursive solution.

So I drafted an answer without divisions that assumes non-zero values. Get the answer by calling: productize(arr, 1, 0, n-1)
Here the last two numbers are the starting and ending indeces of the portion of the array to "productize", and the "1" is the product from the rest of the array:

To save time typing, I'll just use int's, and not worry about production-quality- or even Java, particularly...

/** To fill your array, call:  Productize.compute(myIntArray);
 */
class Productize {
    private static int getProduct(int[] arr, int baseProduct, int start, int end) {
        int product = arr[start];
        while (++start <= end) {
            product *= arr[start];
        }
        return product;
    }

    // apply the baseProduct to a section of the array
    private static int productize(int[] arr, int baseProd, int start, int end) {
        int diff = start - end;
        if (diff = 0) {                            // just one element left
            arr[start] = base;
        } else if (diff == 1) {                    // or two
            arr[start] = baseProd * arr[end];   
            arr[end]   = baseProd * arr[start];   
        } else {                                   // diff is 2 or more, so 3 or more items
            int mid = (start + end) / 2;           // partition the array
            int prod = getProduct(mid+1, end);          // get the right side's product
            productize(arr, prod*baseProd, start, mid); // apply it * base to the left
            int prod = getProduct(start, mid);          // get the left side's product
            productize(arr, prod*baseProd, mid+1, end); // apply it * base to the right
        }
    }

    // To fill your array, call:  Productize.compute(myIntArray);
    public static int compute(int[] arr) {
        productize(arr, 1, 0, arr.length);  // is it length, or size...  Eclipse knows!
    }
}