Necessary and Sufficient

Question: There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

Answer: Solving this without division is pretty easy - you'd just multiply all items except the value at the index you are calculating. The challenge comes in the run time restriction - O(n). The first solution that comes to mind involved looping through all n items in the array and for each of these looping through all n items again to calculate the value of the output array. This, however, has running time ~ O(n²). But, we can use a clever bit of memoization to get round this. We know that to calculate the product of all items for the i-th element in the output array we need the product of the items below i (hereafter the "below product" for i) and the product of the items above i. (hereafter the "above product" for i) Furthermore, when calculating the "below product" for i we can use the "below product" for i-1, which in turn can use the "below product" for i-2. The same thing applies for the "above product". This observation - which is the same sort of memoization you'd use in calculating factorials - means we can formulate a solution which exhibits linear, O(n) run time. Here's my code in Java:

class Main
{
    public static void main(String[] args)
    {
        int[] input = new int[] {3,6,2,1,8,9};
        long[] modified = new long[input.length];

        long runningProduct=1;

        for(int i=0; i< input.length; i++)
        {
            // keep track of the product of the elements below the i-th element
            modified[i] = runningProduct;
            runningProduct *= input[i];
        }

        runningProduct=1;
        for(int i= input.length-1; i>=0; i--)
        {
            // keep track of the product of the elements above the i-th element
            modified[i] *= runningProduct;
            runningProduct *= input[i];
        }

        for(int i=0; i< modified.length; i++)
            System.out.println(modified[i]);
    }
}

And here's my C# code which is almost identical:

        public static void Main()
        {
            var input = new int[] {3,6,2,1,8,9};
            var modified = new long[input.Length];

            long runningProduct=1;

            for(int i=0; i< input.Length; i++)
            {
                // keep track of the product of the elements below the i-th element
                modified[i] = runningProduct;
                runningProduct *= input[i];
            }

            runningProduct=1;
            for(int i= input.Length-1; i>=0; i--)
            {
                // keep track of the product of the elements above the i-th element
                modified[i] *= runningProduct;
                runningProduct *= input[i];
            }

            for(int i=0; i< modified.Length; i++)
                Console.WriteLine(modified[i]);
        }