# Products of an Array

More algorithm fun today, here’s our problem courtesy of Interview Cake. Mmm, cake.

Given an array of numbers, for each index find the product of every integer except the integer at that index.

For example, we’re given:

`[1, 7, 3, 4]`

Our method needs to calculate the products like this:

`[7*3*4, 1*3*4, 1*7*4, 1*7*3]`

Which results in:

`[84, 12, 28, 21]`

Sounds simple enough, right? Well, there’re 2 pretty big limitations:

The first, we can’t use division. Otherwise we’d simply be able to find the product of the entire array then divide by each element.

`arr = [1, 7, 3, 4]product = arr.inject(:*)result = []`
`arr.each_with_index do |value, index|  result[index] = product / valueend`
`result`

And second, we’ll need to account for an input array containing any zeros. Multiplying by zero equals zero, so if we add a zero (or two) to our array we don’t want to end up with a bunch of zeros.

`arr = [1, 7, 0, 3, 4]7 * 0 * 3 * 4 = big fat zero`

### A Basic Solution

A pretty simple solution would be nested each statements where we skip the inner iteration if it means multiplying the current element into the product (or if the current element is 0):

`arr = [1, 7, 0, 3, 4]result = []`
`arr.each do |value|    result << 1    arr.each do |value2|      next if value2 == 0 || value == value2      result[-1] *= value2    end  end`
`result`

That quite nicely takes care of the problem’s limitations. However it uses a nested loop, which means the time complexity of this solution is O(n²). The bigger our input array gets, the longer it will take since we are completely iterating through our every element for every element in the array — overall, pretty inefficient.

### There Has to Be a Better Way!

We can instead split our array and iterate over it from the left and the right. As we go, we’ll find the product of those elements we’re going through, then find the product of the left and right products.

`n = arr.lengthresult = []`
`left = 1 # temp value for finding productsindex = 0 # iterate from the left`
`while index < n do  result[index] = left  left *= arr[index] unless arr[index] == 0`
`  index += 1end`
`right = 1 # temp value for finding productsindex = n - 1 # iterate from the right`
`while index >= 0 do  result[index] *= right  right *= arr[index] unless arr[index] == 0`
`  index -= 1end`
`result`

While not as elegant overall (this solution gives us more lines and some repetition) we’ll reduce our time complexity to O(n). We do iterate over the array twice which actually gives us O(2n), but we can drop the 2 because it’s a constant input.

Like what you read? Give Catherine Kwak a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.