Home

# Daily Coding Problem #2 - A Product Array

February 18, 2019

## Problem

This problem was asked by Uber. 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?

## Thoughts

• Calculate the product of all elements using 1 pass.
• Construct the new array by iterating through the input array again with `new_array[i] = product_in_step1 / array[i]`
• This only work under the assumption that there is no 0 in the array 🤷‍♂️.

## Tests

``````package daily_coding_problem_in_go

import "testing"

var productArrayTests = []struct {
in  []int
out []int
}{
{[]int{1, 2, 3, 4, 5}, []int{120, 60, 40, 30, 24}},
{[]int{3, 2, 1}, []int{2, 3, 6}},
}

func TestProductArray(t *testing.T) {
for _, tc := range productArrayTests {
if actual := ProductArray(tc.in); !Equal(actual, tc.out) {
t.Errorf("%v, expected %v, got %v", tc.in, tc.out, actual)
}
}
}
``````

## Implementation

``````package daily_coding_problem_in_go

func ProductArray(arr []int) []int {
product := arr
result := make([]int, len(arr))

for _, e := range arr[1:] {
product *= e
}

for i, e := range arr {
result[i] = product / e
}

return result
}
``````

Time Complexity: O(n)

Without division, the idea is:

• Input: `arr = [1, 2, 3, 4, 5]`
• Calculate `left = [1, 1*1, 1*1*2, 1*2*3, 1*2*3*4, 1*2*3*4*5]` = `[1, 1, 2, 6, 24]`
• Calculate `right = [5*4*3*2*1, 5*4*3*2, 5*4*3, 5*4, 1]` = `[120, 60, 20, 5, 1]`
• `result = [120, 60, 40, 30, 24]` where `result[i] = left[i] * right[i]`

``````func ProductArray2(arr []int) []int {
size := len(arr)
left := make([]int, size)
right := make([]int, size)
result := make([]int, size)

for i := 0; i < size; i++ {
left[i] = 1
right[i] = 1
}

for i := 1; i < size; i++ {
left[i] = arr[i-1] * left[i-1]
}

for i := size - 2; i >= 0; i-- {
right[i] = arr[i+1] * right[i+1]
}

for i := 0; i < size; i++ {
result[i] = left[i] * right[i]
}

return result
}
``````

Time Complexity: O(n) despite the solution looks a tad more complicated.