Given an array of numbers, return array of products of all other numbers 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 &lt; 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 &lt; 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?
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 &lt; 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 &lt; 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.