Java Daily Coding Problem #002

Daily Coding Problem is a website which will send you a programming challenge to your inbox every day. I want to show beginners how to solve some of these problems using Java, so this will be an ongoing series of my solutions. Feel free to pick them apart in the comments!

Problem

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can't use division?

Strategy

Spoilers! Don't look below unless you want to see my solution!

In the worst case, every element of the returned array of length N will be the product of N-1 other numbers, so this will be an O(N²) solution.

If, instead, we first multiply all of the elements of the given array together (O(N)), then, for each element of the returned array, divide the product by the element at that index in the given array, we instead have an O(N) + O(N) = O(N) solution.

Code

The most straightforward way to do this is to multiply all the array elements together first, then divide by the element at index i to get the element at index i of the returned array:

  public static int[] codingProblem002 (int[] given) {

    int product = 1;

    for (int element : given) 
      product *= element;

    final int len = given.length;
    int[] retval = new int[len];

    for (int i = 0; i < len; ++i)
      retval[i] = product / given[i];

    return retval;
  }

This solution requires N multiplications, N divisions, and at least three traversals of primitive arrays of length N. We can rearrange the solution slightly and initialise the return array the given array as we calculate the product:

  public static int[] codingProblem002 (int[] given) {

    int product = 1;
    final int len = given.length;
    int[] retval = new int[len];

    for (int element : given) {
      product *= element;
      retval[i] = element;
    }

    for (int i = 0; i < len; ++i) 
      retval[i] = product / retval[i];

    return retval;
  }

But this still requires walking the given array in the first for loop, as well as the revtal array, then walking the retval array again in the second for loop. I find myself really wanting pointers in Java right now.

To solve this without using division, we can iterate over the given array N times, multiplying each element in the returned array (except the i-th one) by the i-th element of the given array:

  public static int[] codingProblem002 (int[] given) {

    final int len = given.length;
    int[] retval = new int[len];

    // initialise all elements of `retval` to 1
    Arrays.fill(retval, 1);

    for (int i = 0; i < len; ++i) {
      for (int j = 0; j < len; ++j) {
        if (j == i) continue;
        retval[j] *= given[i];
      }
    }

    return retval;
  }

This is an O(N²) solution.

I'm not extremely happy with my solutions here and would love it if someone could show a more performant way of completing this coding challenge!

All the code for my Daily Coding Problems solutions is available at github.com/awwsmm/daily.

Suggestions? Let me know in the comments.