Get Products with O(n) Time Efficiency

George
Oct 06
1.4k
0
6

Article

Note: this article is published on 07/20/2024.

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,

Algorithm Efficiency (07/20/2024)
Get Common SubString from two Strings (10.03.2021)
- Get String ASCII Value in C# (10/03/2021)
Valid Parentheses (12/30/2021)
Min Stack (12/30/2021)
Get Products with O(n) Time Efficiency (07/20/2024) --- this article

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

BigO.html

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;
}