## Problem Statement

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?

## Solution: Brute force Strategy

Refer the code on the link http://rextester.com/XJDMV96017

```
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
/*
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?
*/
var input = new []{1, 2, 3, 4, 5};
var output = new int[5];
// O(n^2) Approach
for(int i = 0; i < output.Length; i++){
output[i] = 1;
for(int j = 0; j < input.Length; j++){
if(j == i){
continue;
}
output[i] *= input[j];
}
}
Console.WriteLine(string.Join(", ", output));
}
}
}
```

## Solution: Using Array Multiplication Results

Array | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

Left | 1 | 1 | 2 | 6 | 24 |

Right | 120 | 60 | 20 | 5 | 1 |

Left x Right | 1*120 | 1*60 | 2*20 | 6*5 | 24*1 |

Result | 120 | 60 | 40 | 30 | 24 |

From the above information, we can calculate result by multiplying the left and right array.

#### Pseudo Code

We precalculate the left and right array, left is calculated by multiplying the elements from left to right keeping the first entry as 1 and right is calculated in reverse by keeping the last value as 1 and multiplying to the first index.

Refer the code on the link https://rextester.com/OZTL26198

```
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
/*
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?
*/
var input = new []{1, 2, 3, 4, 5};
var n = input.Length;
var left = new int[n];
var right = new int[n];
left[0] = 1;
right[n - 1] = 1;
// Left Multiplication - 1, 1, 2, 6, 24
for(int i = 1; i < n; i++){
left[i] = left[i - 1] * input[i - 1];
}
// Right Multiplication - 120, 60, 20, 5, 1
for(int i = n - 2; i > -1; i--){
right[i] = right[i + 1] * input[i + 1];
}
for(int i = 0; i < n; i++){
Console.Write(left[i]*right[i] + (i == n - 1 ? "" : ","));
}
}
}
}
```

# Additional Approaches

## Log Approach

We use the Log based approach to calculate the result.

```
[a, b, c, d]
product = a * b * c * d
log(product) = log(a * b * c * d)
log(product) = log(a) + log(b) + log(c) + log(d)
product = antilog(log(a) + log(b) + log(c) + log(d))
product = 10 ^ (log(a) + log(b) + log(c) + log(d))
product = Math.Pow ( 10, (log(a) + log(b) + log(c) + log(d)))
// We precalculate the log of product and use it to divide by element
// log a / b = log a - log b
foreach element in [a, b, c, d]
// 10 ^ log (product / element)
// Power to 10 will act as antilog for log with base 10
result.Add( 10 ^ ( log(product) - log(element)) )
```