using System;

/*

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].

*/

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello UBER");

        // TEST CASES

        //int[] arrInput = {1,2,3,4,5,6,7,8,9,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2};

        //int[] arrInput = {1,2,3};

        int[] arrInput = {1,2,3,4,5};

        int counter = QuadraticComplexity(arrInput, true);

        Console.WriteLine("Quadratic: Array Length " + arrInput.Length + "\nSolved in " + counter.ToString() + " passes");

        Console.WriteLine("");

        counter = DoubleLinearComplexity(arrInput, true);

        Console.WriteLine("DoubleLinear: Array Length " + arrInput.Length + "\nSolved in " + counter.ToString() + " passes");

    }

    // O(n*m) number of elements in input * number of elements in output

    private static int QuadraticComplexity(int[] arrInput, bool showResults)

    {

        int counter = 0;

        int[] arrOutput = new int[arrInput.Length];

        for (int i = 0; i < arrInput.Length; i++)

        {

            arrOutput[i] = 1;

            for (int j = 0; j < arrInput.Length; j++)

            {

                counter++; // this operation includes outer loop pass, so no need to increment counter in outer loop

                if( i != j)

                    arrOutput[i] *= arrInput[j]; 

            }

        }

        if (showResults) ShowArrayElements(arrOutput);

        return counter;

    }

    // O (n+m) number of element in input + number of elements in output

    private static int DoubleLinearComplexity(int[] arrInput, bool showResults)

    {

        int counter = 0;

        int[] arrOutput = new int[arrInput.Length];

        int total = 1;

        // first pass multiply all

        for(int i = 0; i < arrInput.Length; i++)

        {

            counter++;

            total *= arrInput[i];

        }

        // second pass divide and save result in array

        for(int i = 0; i < arrInput.Length; i++)

        {

            counter++;

            arrOutput[i] = total / arrInput[i];

        }

        if (showResults) ShowArrayElements(arrOutput);

        return counter;

    }

    private static void ShowArrayElements(int[] myArr) 

    {

        foreach (int e in myArr)

            Console.Write(e.ToString() + " ");

        Console.WriteLine("");

    }

}