Given an array of numbers, return array of products of all other numbers

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 result[] = new BigInteger[input.length]; for (int i = 0; i < input.length; i++) { result[i] = calculateProduct(input, i); } return result; } private static BigInteger calculateProduct(int[] input, int exceptIndex) { BigInteger result = BigInteger.ONE; for (int i = 0; i < input.length; i++) { if (i == exceptIndex) { continue; } result = result.multiply(BigInteger.valueOf(input[i])); } return result; } 

Complexity:

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

Is there any better or efficient way to do this apart from what I have so that complexity can be reduced?

Answer 1

The Time Complexity is indeed: \$\mathcal{O}(n^2)\$.

You can optimize it to \$\mathcal{O}(n)\$ by calculating the total product of all elements in the source array, and then looping over the array and dividing the product by each element to get the product excluding that particular element.

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; } 

EDIT: The above code assumes that none of the numbers is 0 in the input array.

Answer 2

Criticism of original code: it is \$\mathcal{O}(n^2)\$ time, even assuming the BigInteger calculations are constant relative to the input size.

To do this in \$\mathcal{O}(n)\$ time without division, make two arrays. In one, calculate an increasing product from left to right. In the other, calculate an increasing product from right to left. You should be able to generate each array in linear time.

private BigInteger[] buildIncreasingArray(int[] numbers) { BigInteger[] results = new BigInteger[numbers.length]; results[0] = BigInteger.ONE; for (int i = 1; i < results.length; i++) { results[i] = results[i - 1].multiply(BigInteger.valueOf(numbers[i - 1])); } return results; } private BigInteger[] buildDecreasingArray(int[] numbers) { BigInteger[] results = new BigInteger[numbers.length]; results[results.length - 1] = BigInteger.ONE; for (int i = results.length - 2]; i >= 0; i++) { results[i] = results[i + 1].multiply(BigInteger.valueOf(numbers[i + 1])); } return results; } public BigInteger[] calculateSkipProducts(int[] numbers) { if (numbers == null || numbers.length == 0) { throw new IllegalArgumentException("input cannot be empty"); } BigInteger[] fromLeft = buildIncreasingArray(numbers); BigInteger[] fromRight = buildDecreasingArray(numbers); BigInteger[] results = new BigInteger[numbers.length]; for (int i = 0; i < results.length; i++) { results[i] = fromLeft[i].multiply(fromRight[i]); } return results; } 

This will still be \$\mathcal{O}(n)\$ in space and time if the BigInteger calculations run in constant time. It makes a constant number of arrays (three), so that's still linear in space. It iterates over the arrays a constant number of times (once each), so still linear in time. There's an argument that the BigInteger calculations will be non-constant relative to the size of the input array. So that could increase time and space to something like \$\mathcal{O}(n \log{n})\$.

As already stated, you can only get \$\mathcal{O}(1)\$ in space if you modify the original array and you can only get \$\mathcal{O}(n)\$ in time then if you generate the product and divide.

So you must assume that all the answers will fit in int without overflow and that none of the input are zero if you want constant space and linear time. We can already be sure that int operations each occur in constant time.

It is not necessary for the full product to fit in int. You can store it in a long.

I haven't tested this. Be wary of syntax or bounding errors.

Nothing to do with functionality, but the standard indent in Java is four columns.