# The Unconventional Guide to A Product Array Puzzle

## 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 |
---|---|---|---|---|---|

Multiplication with Previous | 1 | (1)*2 | (1*2)*3 | (123)*4 |
(123*4)*5 |

Result | 1 | 2 | 6 | 24 | 120 |

Reverse Array | 5 | 4 | 3 | 2 | 1 |

Multiplication with Previous | 5 | (5)*4 | (5*4)*3 | (543)*2 |
(543*2)*1 |

Reverse Result | 5 | 20 | 60 | 120 | 120 |

From the above information, we can calculate Reverse Multiplication for the array and use it with Normal Multiplication to achieve the desired output.

For the above example, we could

#### Pseudo Code

We first calculate the reverse Matrix multiplication of

[1, 2, 3, 4, 5] as [120, 60, 20, 5, 1]

```
// Reverse Matrix Multiplication
temp = 1
Loop from n=4 to n=1
Output[n]= temp
Output[n-1]= temp * input[n] = 5
End
```

Secondly we use the above reverse Matrix calculation with the normal multiplication

[1, 2, 3, 4, 5] as [1, 2, 6, 24, 120]

```
// Use Reverse Multiplied output with input
temp = 1;
Loop from n=0 to n=4
Output[n] = temp * output[n];
temp *= input[n];
End
```

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

```
//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[input.Length];
// Reverse Multiplication - 1, 5, 20, 60, 120
// Stored as - 120, 60, 20, 5, 1
var temp = 1;
for(int i = input.Length - 1; i > 0; i--){
output[i] = temp;
temp *= input[i];
output[i - 1] = temp;
}
temp = 1;
for(int i = 0; i < input.Length; i++){
output[i] = temp * output[i];
temp *= input[i];
}
Console.WriteLine(string.Join(", ", output));
}
}
}
```