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