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.