Product Array

README.txt

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?

Program.cs

private static long[] ProductArray(int[] inputArray)
{
    int n = inputArray.Length;
    long[] outputArray = new long[n];
    long[] leftToRight = new long[n];
    long[] rightToLeft = new long[n];

    // product left to right
    leftToRight[0] = inputArray[0];
    for (int i = 1; i < n; i++)
    {
        leftToRight[i] = leftToRight[i - 1] * inputArray[i];
    }

    // product right to left
    rightToLeft[n - 1] = inputArray[n - 1];
    for (int i = n - 2; i >= 0; i--)
    {
        rightToLeft[i] = rightToLeft[i + 1] * inputArray[i];
    }

    for (int i = 0; i < n; i++)
    {
        long left = i - 1 >= 0 ? leftToRight[i - 1] : 1L;
        long right = i + 1 < n ? rightToLeft[i + 1] : 1L;
        outputArray[i] = left * right;
    }

    return outputArray;
}