Return the nth row of the Pascal's triangle.

Approach: If we see nth row of Pascal triangle is binomial coefficient i.e. nC0, nC1, nC2, nC3 ... nCn so we don't need to calculate previous rows to get the nth row. 

We also can apply optimization while calculating nCr. Here is how -

nC0 = 1

nCr / nCr-1 = (!n / !r * !n - r) / (!n / !r - 1 * !n - r + 1) = (!r - 1 * !n - r + 1) / (!r * !n - r) = (n - r + 1) / r

nCr / nCr-1 = (n - r + 1) / r

nCr = (nCr-1 * (n - r + 1)) / r 

That is how we can calculate the next value and we are set. But we will have a problem for big value of n where  nCr-1 * (n - r + 1) may overflow. 

This product should be divisible by r so we can avoid the overflow by dividing before the multiplication. Calculate GCD of (n - r + 1) and r and then the we can write the above expression as -

nCr = (nCr-1 / (r / gcd)) * ((n - r + 1) / gcd)

        public static IList<int> GetPascalTriangleRow(int rowIndex)

        {

            List<int> result = new List<int>();

            if (rowIndex < 0)

            {

                return result;

            }

            int prev = 1; // nC0 = 1

            result.Add(prev);

            for (int i = 1; i <= rowIndex; ++i)

            {

                int gcd = GCD(rowIndex - i + 1, i); // To avoid overflow

                int curr = (prev / (i / gcd)) * ((rowIndex -i + 1) / gcd); //(prev * (rowIndex - i + 1)) / i;

                result.Add(curr);

                prev = curr;

            }

            return result;

        }

        public static int GCD(int m, int n)

        {

            while (n > 0)

            {

                int r = m % n;

                m = n;

                n = r;

            }

            return m;

        }