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`

^{2}`)`

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`

^{2}`)`

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.

## Discussion (3)

Java 8:

Fails for elements with a 0, obviously, could be worked around with filtering.

Hey @andrew

Awesome job.

I recently started doing these problems(in Python) and sharing solutions on a public github repo.

But after only 2, I got really busy.

Looking at your posts gave me motivation, I will try to get going with them again.

Thanks man.

"I find myself really wanting pointers in Java right now."

What is it you wish to accomplish with pointers that you can't do in Java here?

Isn't the index as good as a pointer for this?