Pascal’s Triangle
Loveena Saran
Posted on January 31, 2022
Deduction made from how the Pascal's triangle is constructed:
The boxes at the start and end of the list are always set to '1'
Initially the first 2 levels do not have any adding up of elements and the process of adding starts from the 3rd level
Adding up the previous level answer leads to the new numbers at the center of the triangle
How to approach this problem?
- We can keep a pointer to here 'i' for each level of the triangle
- Also if we notice there are center boxes that grow in triangular pattern.
Notice when level is '1' we have '0' elements to be added from previous levels.
At level 1 --> 0 elements are formed by adding
At level 2 --> 1 elements are formed by adding
At level 3 --> 2 elements are formed by adding
and so on...
- we can have a 'j' variable that we initialize when we are at 1st level of 'i'.
- Here we are initializing 'j' to be 'zero' and less than 'i'.
'i' and 'j' values Serve multiple purposes in this problem
- 'i' indicates each level and 'j' indicates the elements formed by adding up previous elements.
- 'j' runs at a 1 less than 'i' as it starts from '0' and creates boxes at each level.
- As the answer is stored in List i.e (List of Lists). We can to retrieve the previous level data and add this to form the current value.
Code:
for(int i=1; i<=numRows; i++){
for(int j=0; j<i; j++){
- For the first and the last box we want to add '1'
for(int i=1;i<=numRows;i++){
for(int j=0; j<i; j++){
if(j==0 || j==i-1){ // add '1' to first box and last box
curr.add(1); // Add to list curr
}
-For boxes at the center ranging from (1:i-1)
for(int i=1;i<=numRows;i++){
List<Integer> curr = new ArrayList<>();
for(int j=0;j<i;j++){
if(j==0 || j==i-1){
curr.add(1);
}
else{
curr.add(levels.get(i-1).get(j)+ levels.get(i-1).get(j-1)); // to form new elements by adding values from previous levels
}
}
Do like if you found this helpful. This would help me learn and create new articles like this.
Thanks!
Posted on January 31, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.