Programming Problems - Pascal Triangle

In mathematics, Pascal's Triangle is a triangular array of binomial coefficients.

This exercise is the same as the previous exercise. Deliberately did not use the name Pascal's Triangle and instead called it as Number Pattern. That is because if I had used the name Pascal's Triangle then one could search in Google and get all the information about it. Then the real learning would not happen.

First few rows of Pascal's Triangle are given below.

      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1
 1 5 10 10 5 1
1 6 15 20 15 6 1


The Pascal Triangle has the following properties.

1. Assuming that the row and the column numbers start from 1, the number of columns in a row is equal to the row number. (No. of Columns = RowNum).
2. In a row, the value of the first and last columns are always 1.
3. In any row, the value of a cell is the sum of its adjacent cells in the previous row. CellVal(RowNum, ColNum) = CellVal(RowNum - 1, ColNum - 1) + CellVal(RowNum - 1, ColNum)

The problem is to find the cell value, given a row number and a column number.

NumberPattern

Implement the class NumberPattern with the following public method.

public int getCellVal(int nRowNum, int nColNum);

Please notice that the Pascal's Triangle exhibits vertical symmetry. That means in any row the first cell value is the same as the last, the second is same as the second from last and so on. In a row, we never have to calculate a cell value beyond the midpoint. After the midpoint, the cell values start repeating. For example, to calculate the value of cell number 99 for row 100, which is second from last, it is just enough to calculate the value of cell number 2 of row 100 which is second from the beginning. I have seen several solutions which do not take advantage of this symmetry.

The major point I wanted to highlight in this exercise is not all the problems could be solved using the basic data structures knowledge. For example, the problem like MaxSubsequenceSum can be solved using the basic Computer Science knowledge even if we are coming across the problem for the very first time. But this exercise, the Pascal's Triangle can be solved efficiently using the formula and one would know the formula only if one has already read about the Pascal's Triangle. This is the point I wanted to highlight. It is important that we continuously read and relentlessly seek knowledge as not every problem can be solved using the knowledge we possess. We need to continuously add to our knowledge, keep it updated and constantly keep learning new things.

The formula for Pascal's Triangle is given below. (RowNum and ColNum are 1 based. They do not start from zero instead they start from 1)

CellVal(RowNum, ColNum) = (RowNum - 1)! / (ColNum - 1)! * (RowNum - ColNum)!

This is equivalent to

Numerator = R-1 * R-2 * R-3 * ...... ColNum-1 times
Denominator = (ColNum - 1)!

I strongly urge the readers to make a sincere attempt in implementing the solution. I am providing my implementation so that you can compare it with yours. Looking straightaway at my solution may not be as helpful as making a physical attempt to solve the problem even if your solution is incomplete or not perfect.

You could also carry your source code in a public repository hosted on GitHub and if you prefer you could share the link to your source code in the comment section so that other readers could take a look at it and provide their comments.

Please provide your support and express your encouragement by using the social buttons provided below and share this effort with others.

Here is the link to my solution.