Post
Ask Question

Get Products with O(n) Time Efficiency

I came from science, I have never had a chance to learn or play a game such as an algorithm in my student career. Most algorithm problems I met are in interviews. In my view, these kinds of tricks are just boby level games, but if you did not have related training previously, you might not get the solution immediately. So, I will open a topic, or series, to record the algorithm questions I met or I played previously (10/03/2021, from my first algorithm article).

This series will include,

I will add more on this topic probably from my notes or practice code.

A - Introduction

This is the structure of this article,

  • A - Introduction
  • B - Question
  • C - Main
  • D - Order (2) Solution
  • E - Order (1) Solution

B - Question

The question given is below:

// Required: O(n): Linear time
// input: int[] ints = { 2, 3, 5, 7 };
// 
// output: --- Get Products of all numbers with
//      Position i: take the number off or make it to 1 
//  such like
//  1: 1*3*5*7 = 105
//  2: 2*1*5*7 = 70
//  3: 2*3*1*7 = 42
//  4: 2*3*5*1 = 30

// You cannot make a product and make a division

C - Main Program

Main:

        public static void Main()
        {

            //int[] ints = { 2, 3, 5, 7, 11 };
            int[] ints = { 2, 3, 5, 7 };

            Console.Write($" Input: {{ 2, 3, 5, 7 }}");
            Console.WriteLine();
            Console.WriteLine();

            ints = GetProducts(ints);

            Console.Write($" Output: ");
            Console.WriteLine();

            String[] products = { "1*3*5*7", "2*1*5*7", "2*3*1*7", "2*3*5*1" };

            for (int i = 0; i < ints.Length; i++)
            {
                Console.Write($" {products[i]} = {ints[i]}");
                Console.WriteLine();
            }

            Console.ReadLine();
        }

D - Order (2) Solution

Order 2:

        static int[] GetProducts(int[] A)
        {
            int[] L = new int[A.Length]; // left wing
            int[] R = new int[A.Length]; // right wing
            int[] P = new int[A.Length]; // Product

            int LP = 1; // left product
            int RP = 1; // right product

            for (int i = 0; i < A.Length; i++)
            {
                P[i] = 1;
                for(int j = 0; j < A.Length; j++)
                {
                    if(i != j)
                    P[i] = P[i]*A[j];

                }
            }
            return P;
        }

This algorithm is working, but with Order (2) solution: measured from 

E - Order (1) Solution

Order 1:

        static int[] GetProducts(int[] A)
        {
            int[] L = new int[A.Length]; // left wing
            int[] R = new int[A.Length]; // right wing
            int[] P = new int[A.Length]; // Product

            int LP = 1; // left product
            int RP = 1; // right product

            for (int i = 0; i < A.Length; i++)
            {
                L[i] = LP;
                LP = LP * A[i];

                R[A.Length - 1 - i] = RP;
                RP = RP * A[A.Length - 1 - i];

                if (R[i] != 0)
                {
                    P[i] = L[i] * R[i];
                    P[P.Length - 1 - i] = L[L.Length - 1 - i] * R[A.Length - 1 - i];
                }
            }
            return P;
        }

Here, we use one dimension calculation to finish the task, it is a one order calculation:

References


Similar Articles