Get Products with O(n) Time Efficiency

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,

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#

Copy

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

C#

Copy

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

C#

Copy

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

C#

Copy

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

References

 

Up Next
    Ebook Download
    View all
    Learn
    View all