Problem

Submissions

Hints & solutions

Discuss

Find Kth row of Pascal's Triangle

Easy

0/40

Average time to solve is 15m

Contributed by

12 upvotes

Asked in companies

Problem statement

You are given a non-negative integer 'K'. Your task is to find out the Kth row of Pascal’s Triangle.

In Mathematics, Pascal's triangle is a triangular array where each entry of a line is a value of a binomial coefficient. An example of Pascal’s triangle is given below.

Example :-

INPUT : K = 2
OUTPUT: 1 1

In the above example, K = 2, Hence the 2nd row from the top of pascal’s triangle, as shown in the above example is 1 1.

INPUT   : K = 4
OUTPUT  : 1 4 6 4 1

In the above example, K = 4, Hence the 4th row from the top of pascal’s triangle, as shown in the above example is 1 3 3 1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.

The first and the only line of each test case contains a single integer “K”.

Output Format:

For every test case, print a single line containing 'R' space-separated integers showing the Kth row of pascal’s triangle, where 'R' is the number of elements in a particular row.

The output of each test case will be printed in a separate line.

Note

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= K <= 50

Where ‘T’ is the number of test cases, ‘K’ is the input row number.

Time limit: 1 sec.

Sample Input 1:

Sample Output 1:

Explanation of sample input 1:

For K = 1, the elements of the first row of the pascal’s triangle will be printed, Hence the output is 1.

For K = 2, the elements of the second row of the pascal’s triangle will be printed, Hence the output is 1 1.

For K = 3, the elements of the third row of the pascal’s triangle will be printed, Hence the output is 1 2 1.

For K = 4, the elements of the fourth row of the pascal’s triangle will be printed, Hence the output is 1 3 3 1.

Sample Input 2:

Sample Output 2:

1 5 10 10 5 1 
1 4 6 4 1 
1 6 15 20 15 6 1 
1 1
1 8 28 56 70 56 28 8 1

Hint 1

Hint 2

Hint 3

Hint 4

Can you think of a recursive algorithm?

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Naive Approach

In this approach, we find the row elements of the previous row using recursion, and based on the values of previous row elements, we will evaluate the current row elements.

We are given a function kthRow() which takes an integer ‘K’ as the only parameter and returns an integer vector. This is the definition of our recursive function too.
As the base condition of our recursive function, we will check if ‘K’ is equal to 1 or not. If ‘K’ is 1, we will return the vector containing 1.
Now we will call our recursive function kthRow() with K - 1 as our new parameter to store the previous row elements.
Now by adding the previous row elements, we will find the current row elements and then return the current row.

Time Complexity

O(N ^ 2), where ‘N’ is the input row index.

Due to recursive calls, we are doing work in the order of (N * (N - 1)) / 2. Hence our worst-case time complexity is O(N ^ 2).

Space Complexity

O(N ^ 2), where ‘N’ is the input row index.

We are taking a vector and doing recursive calls so total space taken will be of the order of (N * (N - 1)) / 2. Hence the worst-case space complexity will be O(N ^ 2).

(100% EXP penalty)

Find Kth row of Pascal's Triangle

Console