I am not able to solve this question

#1

Please help me on how to approach this question, I’m not able to device a method as to how do I take sum of elements present in the previous row to form elements in the next row

#2

Hey start with two rows
1
1 1

Now for each row take first element as 1 and rest as arr[i][j]=arr[i-1][j-1]+arr[i-1][j]
and now take its last element as 1

So for 3rd row (1 , 1+1 ,1 ) ==(1,2,1)
for 4th row (1,1+2,2+1,1) ==(1,3,3,1)
for 5th row (1,1+3,3+3,3+1,1)==(1,4,6,4,1)
and so on…

#3

So do we need to use array for this question?

#4

Yes @chaturvedia336We have to use array in this

#5

I might also have done this using arrays, but this question was way before the array section. So I thought there might be some other trick to solve this.

1 Like
#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#7

Is there any other way by which we can solve this without using an array?

#8

Hey @chaturvedia336
Yes u can,here are the 3 methods
( O(n^3) time complexity )
Number of entries in every line is equal to line number. For example, the first line has “1”, the second line has “1 1”, the third line has “1 2 1”,… and so on. Every entry in a line is value of a Binomial Coefficient. The value of i th entry in line number line is C(line, i) . The value can be calculated using following formula.

C(line, i) = line! / ( (line-i)! * i! )

( O(n^2) time and O(1) extra space )
This method is based on method 1. We know that i th entry in a line number line is Binomial Coefficient C(line, i) and all lines start with value 1. The idea is to calculate C(line, i) using C(line, i-1) . It can be calculated in O(1) time using the following.

C(line, i) = line! / ( (line-i)! * i! ) C(line, i-1) = line! / ( (line - i + 1)! * (i-1)! ) We can derive following expression from above two expressions. C(line, i) = C(line, i-1) * (line - i + 1) / i So C(line, i) can be calculated from C(line, i-1) in O(1) time

( O(n^2) time and O(n^2) extra space )
If we take a closer at the triangle, we observe that every entry is sum of the two values above it. So we can create a 2D array that stores previously generated values. To generate a value in a line, we can use the previously stored values from array.

#9

This seems to be wrong…
Consider, for example line number 3, 2nd element(i.e 2)… according to this formula, it’s value comes out to be 3 which is incorrect. Please explain?

#10

This is according to 0th indexing
So for 3rd line ,line will be 2
And 2nd element ,i will be 1
So 2!/(2-1)!1!=2