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

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