Another Casual Coder

This problem interestingly enough requires a quick implementation of the millennium-old GCD - Greatest Common Divisor. It is a geometric problem where what you need to do is check whether point V2 belongs to the same line as points V1 and V0. In order to do so, and to avoid floating-point arithmetic, keep track of the slope of V1 and V0 using the num/den fraction, but reduce it to its irreducible form. In order to do so, you'll need to calculate the GCD between num and den. That can be done using Euclid's algorithm which runs in LogN. Since there is a sorting pre-step involved, the total execution time would be NLogN. Code is down below, cheers, ACC.

Minimum Lines to Represent a Line Chart - LeetCode

Input: stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
Output: 3
Explanation:
The diagram above represents the input, with the X-axis representing the day and Y-axis representing the price.
The following 3 lines can be drawn to represent the line chart:
- Line 1 (in red) from (1,7) to (4,4) passing through (1,7), (2,6), (3,5), and (4,4).
- Line 2 (in blue) from (4,4) to (5,4).
- Line 3 (in green) from (5,4) to (8,1) passing through (5,4), (6,3), (7,2), and (8,1).
It can be shown that it is not possible to represent the line chart using less than 3 lines.

Input: stockPrices = [[3,4],[1,2],[7,8],[2,3]]
Output: 1
Explanation:
As shown in the diagram above, the line chart can be represented with a single line.

public class Solution
{
 public class MyComparerStocks : IComparer
 {
 public int Compare(Object x, Object y)
 {
 int[] dayStock1 = (int[])x;
 int[] dayStock2 = (int[])y;
 return dayStock1[0].CompareTo(dayStock2[0]);
 }
 }
 public int MinimumLines(int[][] stockPrices)
 {
 if (stockPrices.Length <= 1) return 0;
 Array.Sort(stockPrices, new MyComparerStocks());
 Hashtable cache = new Hashtable();
 int retVal = 1;
 int distX = stockPrices[1][0] - stockPrices[0][0];
 int distY = stockPrices[1][1] - stockPrices[0][1];
 int prevNum = 0;
 int prevDen = 0;
 SimplifyFraction(distX, distY, ref prevNum, ref prevDen);
 for (int i = 2; i < stockPrices.Length; i++)
 {
 distX = stockPrices[i][0] - stockPrices[i - 1][0];
 distY = stockPrices[i][1] - stockPrices[i - 1][1];
 int currNum = 0;
 int currDen = 0;
 SimplifyFraction(distX, distY, ref currNum, ref currDen);
 if (prevNum != currNum || prevDen != currDen) retVal++;
 prevNum = currNum;
 prevDen = currDen;
 }
 return retVal;
 }
 private void SimplifyFraction(int a,
 int b,
 ref int num,
 ref int den)
 {
 num = Math.Abs(a);
 den = Math.Abs(b);
 int mul = 1;
 if ((a < 0 && b > 0) || (a > 0 && b < 0)) mul = -1;
 int gcd = GCD(num, den);
 while (gcd > 1)
 {
 num /= gcd;
 den /= gcd;
 gcd = GCD(num, den);
 }
 num *= mul;
 }
 private int GCD(int a, int b)
 {
 while (a != 0 && b != 0)
 {
 if (a > b)
 a %= b;
 else
 b %= a;
 }
 return a == 0 ? b : a;
 }
}

And Happy 15th birthday to my beloved little girl!!!!!!!