Find the Nth row in Pascal’s Triangle
Given a non-negative integer N, the task is to find the Nth row of Pascal’s Triangle.
Note: The row index starts from 0.
Pascal’s Triangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Examples:
Input: N = 3
Output: 1, 3, 3, 1
Explanation:
The elements in the 3rd row are 1 3 3 1.Input: N = 0
Output: 1
Naive Approach:
The simplest approach to solve the problem is to use Recursion. Find the row of the previous index first using recursion and then calculate the values of the current row with the help of the previous one. Repeat this process up to the Nth row.
Below is the implementation of the above approach:
C++
// C++ program to find the Nth // index row in Pascal's triangle #include <bits/stdc++.h> using namespace std; // Function to find the elements // of rowIndex in Pascal's Triangle vector< int > getRow( int rowIndex) { vector< int > currow; // 1st element of every row is 1 currow.push_back(1); // Check if the row that has to // be returned is the first row if (rowIndex == 0) { return currow; } // Generate the previous row vector< int > prev = getRow(rowIndex - 1); for ( int i = 1; i < prev.size(); i++) { // Generate the elements // of the current row // by the help of the // previous row int curr = prev[i - 1] + prev[i]; currow.push_back(curr); } currow.push_back(1); // Return the row return currow; } // Driver Code int main() { int n = 3; vector< int > arr = getRow(n); for ( int i = 0; i < arr.size(); i++) { if (i == arr.size() - 1) cout << arr[i]; else cout << arr[i] << ", " ; } return 0; } // This code is contributed by divyesh072019 |
Java
// Java Program to find the Nth // index row in Pascal's triangle import java.util.ArrayList; public class Beginner { // Function to find the elements // of rowIndex in Pascal's Triangle public static ArrayList<Integer> getRow( int rowIndex) { ArrayList<Integer> currow = new ArrayList<Integer>(); // 1st element of every row is 1 currow.add( 1 ); // Check if the row that has to // be returned is the first row if (rowIndex == 0 ) { return currow; } // Generate the previous row ArrayList<Integer> prev = getRow(rowIndex - 1 ); for ( int i = 1 ; i < prev.size(); i++) { // Generate the elements // of the current row // by the help of the // previous row int curr = prev.get(i - 1 ) + prev.get(i); currow.add(curr); } currow.add( 1 ); // Return the row return currow; } // Driver Program public static void main(String[] args) { int n = 3 ; ArrayList<Integer> arr = getRow(n); for ( int i = 0 ; i < arr.size(); i++) { if (i == arr.size() - 1 ) System.out.print(arr.get(i)); else System.out.print(arr.get(i) + ", " ); } } } |
Python3
# Python3 program to find the Nth # index row in Pascal's triangle # Function to find the elements # of rowIndex in Pascal's Triangle def getRow(rowIndex) : currow = [] # 1st element of every row is 1 currow.append( 1 ) # Check if the row that has to # be returned is the first row if (rowIndex = = 0 ) : return currow # Generate the previous row prev = getRow(rowIndex - 1 ) for i in range ( 1 , len (prev)) : # Generate the elements # of the current row # by the help of the # previous row curr = prev[i - 1 ] + prev[i] currow.append(curr) currow.append( 1 ) # Return the row return currow n = 3 arr = getRow(n) for i in range ( len (arr)) : if (i = = ( len (arr) - 1 )) : print (arr[i]) else : print (arr[i] , end = ", " ) # This code is contributed by divyeshrabadiya07 |
C#
// C# program to find the Nth // index row in Pascal's triangle using System; using System.Collections.Generic; class GFG{ // Function to find the elements // of rowIndex in Pascal's Triangle public static List< int > getRow( int rowIndex) { List< int > currow = new List< int >(); // 1st element of every row is 1 currow.Add(1); // Check if the row that has to // be returned is the first row if (rowIndex == 0) { return currow; } // Generate the previous row List< int > prev = getRow(rowIndex - 1); for ( int i = 1; i < prev.Count; i++) { // Generate the elements // of the current row // by the help of the // previous row int curr = prev[i - 1] + prev[i]; currow.Add(curr); } currow.Add(1); // Return the row return currow; } // Driver code public static void Main(String[] args) { int n = 3; List< int > arr = getRow(n); for ( int i = 0; i < arr.Count; i++) { if (i == arr.Count - 1) Console.Write(arr[i]); else Console.Write(arr[i] + ", " ); } } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find the Nth // index row in Pascal's triangle // Function to find the elements // of rowIndex in Pascal's Triangle function getRow(rowIndex) { let currow = []; // 1st element of every row is 1 currow.push(1); // Check if the row that has to // be returned is the first row if (rowIndex == 0) { return currow; } // Generate the previous row let prev = getRow(rowIndex - 1); for (let i = 1; i < prev.length; i++) { // Generate the elements // of the current row // by the help of the // previous row let curr = prev[i - 1] + prev[i]; currow.push(curr); } currow.push(1); // Return the row return currow; } let n = 3; let arr = getRow(n); for (let i = 0; i < arr.length; i++) { if (i == arr.length - 1) document.write(arr[i]); else document.write(arr[i] + ", " ); } </script> |
1, 3, 3, 1
Time Complexity: O(N2)
Space Complexity: O(N)
Efficient Approach:
Follow the steps below to optimize the above approach:
- Unlike the above approach, we will just generate only the numbers of the Nth row.
- We can observe that the Nth row of the Pascal’s triangle consists of following sequence:
NC0, NC1, ......, NCN - 1, NCN
- Since, NC0 = 1, the following values of the sequence can be generated by the following equation:
NCr = (NCr - 1 * (N - r + 1)) / r where 1 ? r ? N
Below is the implementation of the above approach:
C++
// C++ program to implement the above approach #include <bits/stdc++.h> using namespace std; // Print the N-th row of the Pascal's Triangle void generateNthrow( int N) { // nC0 = 1 int prev = 1; cout << prev; for ( int i = 1; i <= N; i++) { // nCr = (nCr-1 * (n - r + 1))/r int curr = (prev * (N - i + 1)) / i; cout << ", " << curr; prev = curr; } } // Driver Program int main() { int N = 5; generateNthrow(N); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
C
// C program to implement the above approach #include <stdio.h> // Print the N-th row of the Pascal's Triangle void generateNthrow( int N) { // nC0 = 1 int prev = 1; printf ( "%d" , prev); for ( int i = 1; i <= N; i++) { // nCr = (nCr-1 * (n - r + 1))/r int curr = (prev * (N - i + 1)) / i; printf ( ",%d " , curr); prev = curr; } } // Driver Program int main() { int N = 5; generateNthrow(N); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program to implement the above approach import java.io.*; class GFG{ // Print the N-th row of the // Pascal's Triangle static void generateNthrow( int N) { // nC0 = 1 int prev = 1 ; System.out.print(prev); for ( int i = 1 ; i <= N; i++) { // nCr = (nCr-1 * (n - r + 1))/r int curr = (prev * (N - i + 1 )) / i; System.out.print( ", " + curr); prev = curr; } } // Driver code public static void main (String[] args) { int N = 5 ; generateNthrow(N); } } // This code is contributed by shubhamsingh10 |
Python3
# Python3 program to implement the above approach # Print the N-th row of the # Pascal's Triangle def generateNthRow (N): # nC0 = 1 prev = 1 print (prev, end = '') for i in range ( 1 , N + 1 ): # nCr = (nCr-1 * (n - r + 1))/r curr = (prev * (N - i + 1 )) / / i print ( "," , curr, end = '') prev = curr # Driver code N = 5 # Function calling generateNthRow(N) # This code is contributed by himanshu77 |
C#
// C# program to implement the above approach using System; using System.Collections.Generic; class GFG{ // Print the N-th row of the // Pascal's Triangle static void generateNthrow( int N) { // nC0 = 1 int prev = 1; Console.Write(prev); for ( int i = 1; i <= N; i++) { // nCr = (nCr-1 * (n - r + 1))/r int curr = (prev * (N - i + 1)) / i; Console.Write( ", " + curr); prev = curr; } } // Driver code public static void Main(String[] args) { int N = 5; generateNthrow(N); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to implement the above approach // Print the N-th row of the // Pascal's Triangle function generateNthrow(N) { // nC0 = 1 let prev = 1; document.write(prev); for (let i = 1; i <= N; i++) { // nCr = (nCr-1 * (n - r + 1))/r let curr = (prev * (N - i + 1)) / i; document.write( ", " + curr); prev = curr; } } let N = 5; generateNthrow(N); // This code is contributed by suresh07. </script> |
1, 5, 10, 10, 5, 1
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us