Given an array of numbers, return array of products of all other numbers without division?

Question

I was recently asked the following interview question over the phone:

Given an array of integers, produce an array whose values are the product of every other integer excluding the current index.

Example:

[4, 3, 2, 8] -> [3*2*8, 4*2*8, 4*3*8, 4*3*2] -> [48, 64, 96, 24]

I came up with below code:

public static BigInteger[] calcArray(int[] input) throws Exception {
    if (input == null) {
        throw new IllegalArgumentException("input is null");
    }
    BigInteger product = calculateProduct(input);
    BigInteger result[] = new BigInteger[input.length];
    for (int i = 0; i < input.length; i++) {
        result[i] = product.divide(BigInteger.valueOf(input[i]));
    }
    return result;
}

private static BigInteger calculateProduct(int[] input) {
    BigInteger result = BigInteger.ONE;
    for (int i = 0; i < input.length; i++) {
        result = result.multiply(BigInteger.valueOf(input[i]));
    }
    return result;
}

Complexity:

Time Complexity: O(n)
Space Complexity: O(n)

Can we do this in O(n) complexity without division? Also is there any way to reduce space complexity if use simple primitive integer array.

Posted earlier by @mettleap: You can find the algorithm here: https://www.geeksforgeeks.org/a-product-array-puzzle/ — Andreas

SomeDude SomeDude · Accepted Answer · 2018-10-11T01:11:13

Consider an element located at index i. Look to its left, lets say we have a product of elements till the index i-1. Lets call it leftProduct[i] that is product of all elements to the left of element at i. Similarly lets call rightProduct[i] is product of all elements to the right of element at i. Then the result for that index is output[i] = leftProduct[i]*rightProduct[i]

Now think about how to get leftProduct. You simply traverse the array from start and compute a running product and at each element update the leftProduct with the current running product. Similarly you can compute rightProduct by traversing the array from the end. Here you can optimize the space by reusing the leftProduct array by updating it with multiplying the rightProduct.

The below code demonstrates this:

public static int[] getProductsExcludingCurrentIndex( int[] arr ) {
     if ( arr == null || arr.length == 0 ) return new int[]{};
     int[] leftProduct = new int[arr.length];
     int runningProduct = 1;
     //Compute left product at each i
     for ( int i = 0; i < arr.length; i++ ) {
       leftProduct[i] = runningProduct;
       runningProduct = runningProduct*arr[i];
    }
    runningProduct = 1;
    //By reverse traversal, we compute right product but at the same time update the left 
    //product, so it will have leftProduct*rightProduct
    for ( int i = arr.length - 1; i >= 0; i-- ) {
        leftProduct[i] = leftProduct[i]*runningProduct;
        runningProduct = runningProduct*arr[i];
    }
    return leftProduct;
}

Space complexity is O(n) - we use only one array leftProduct, time complexity is O(n).

Space complexity edit:

But if you don't consider the space used for storing output, then this is O(1), because we are storing output in leftProduct itself.

If you strictly don't want extra space then that entails modifying your input array. Solving this by modifying input array as you go is not possible at all at least as far as I know.

Given an array of numbers, return array of products of all other numbers without division?

2 Answers