2
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ can we do this without division in O(n)? and space complexity is still O(n) right? can we do space complexity in O(1) if there is any way? \$\endgroup\$ – user5447339 Oct 10 '18 at 23:13
  • \$\begingroup\$ I don't think we can do this without division in O(n). Also, the space complexity cannot be O(1) here since we are using BigInteger array for our result and input is of primitive int type array. So we cannot modify the input array, we need a new array. \$\endgroup\$ – Apoorv Agarwal Oct 10 '18 at 23:18
  • \$\begingroup\$ let's assume if this was not BigInteger array and it was simple primitive input array? \$\endgroup\$ – user5447339 Oct 10 '18 at 23:19
  • \$\begingroup\$ Then you can directly modify the input array, like input[i] = product/input[i], so that the solution is in place ( O(1) space complexity ) \$\endgroup\$ – Apoorv Agarwal Oct 10 '18 at 23:20
  • \$\begingroup\$ What if one (or more) of the given integers is zero? \$\endgroup\$ – Martin R Oct 11 '18 at 5:10
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.