Java Daily Coding Problem #002
Tags: java, challenge, beginners, dailycodingproblem
Published: 2019-04-22 10:22:41

[Daily Coding Problem](https://dailycodingproblem.com/) 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`<sup>2</sup>`)` 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:

```java
  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`:

```java
  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:

```java
  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`<sup>2</sup>`)` 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](https://github.com/awwsmm/daily).

Suggestions? Let me know in the comments.