Given an integer numRows return the first numRows rows of Pascal's triangle.
In Pascal's triangle:
Input: numRows = 4
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
Explanation: 1st Row has its value set to 1.
All other cells take their value as the sum of the values directly above them
Input: numRows = 5
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Explanation: 1st Row has its value set to 1.
All other cells take their value as the sum of the values directly above them
Input: numRows = 3
Given the row number r and the column number c, find out the element at position (r , c).
The idea is to use an optimal formula of nCr to solve this problem.
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Function to calculate nCr (combinations)
int nCr(int n, int r) {
/* Choosing the smaller value
of r to optimize computation*/
if (r > n - r) {
r = n - r;
}
long long res = 1;
/* Calculate nCr using iterative
method to avoid overflow*/
for (int i = 0; i < r; i++) {
res = res * (n - i);
res = res / (i + 1);
}
return (int)res;
}
public:
// Function to generate Pascal's Triangle up to numRows rows
vector<vector<int>> pascalTriangle(int numRows) {
// Initialize the triangle vector with numRows rows
vector<vector<int>> triangle(numRows);
// Fill the triangle with Pascal's Triangle values
for (int i = 0; i < numRows; i++) {
// Resize current row to i + 1 elements
triangle[i].resize(i + 1);
for (int j = 0; j <= i; j++) {
// Compute and store the value at position (i, j)
triangle[i][j] = nCr(i, j);
}
}
// Return completed Pascal's Triangle
return triangle;
}
};
int main() {
// row number
int r = 5;
// col number
int c = 3;
// Create an instance of the Solution class
Solution sol;
vector<vector<int>> pascalTriangle = sol.generate(r);
/* Check if column number is valid
and retrieve the element at (r, c)*/
if (r >= c && c > 0) {
int element = pascalTriangle[r - 1][c - 1];
cout << "The element at position (" << r << "," << c << ") is: "
<< element << "\n";
} else {
// Print error message if column number is invalid
cout << "Invalid column number!\n";
}
return 0;
}
import java.util.*;
class Solution {
// Function to calculate nCr (combinations)
private int nCr(int n, int r) {
/* Choosing the smaller value
of r to optimize computation */
if (r > n - r) {
r = n - r;
}
long res = 1;
/* Calculate nCr using iterative
method to avoid overflow */
for (int i = 0; i < r; i++) {
res = res * (n - i);
res = res / (i + 1);
}
return (int)res;
}
// Function to generate Pascal's Triangle up to numRows rows
public List<List<Integer>> pascalTriangle(int numRows) {
// Initialize the triangle list with numRows lists
List<List<Integer>> triangle = new ArrayList<>();
// Fill the triangle with Pascal's Triangle values
for (int i = 0; i < numRows; i++) {
/* Create a new row list and
resize it to i + 1 elements*/
List<Integer> row = new ArrayList<>();
for (int j = 0; j <= i; j++) {
//Compute and store value at position (i, j)
row.add(nCr(i, j));
}
triangle.add(row);
}
// Return completed Pascal's Triangle
return triangle;
}
public static void main(String[] args) {
// row number
int r = 5;
// col number
int c = 3;
// Create an instance of the Solution class
Solution sol = new Solution();
List<List<Integer>> pascalTriangle = sol.generate(r);
/* Check if column number is valid
and retrieve the element at (r, c) */
if (r >= c && c > 0) {
int element = pascalTriangle.get(r - 1).get(c - 1);
System.out.println("The element at position (" + r + "," + c + ") is: " + element);
} else {
// Print error message if column number is invalid
System.out.println("Invalid column number!");
}
}
}
from typing import List
class Solution:
# Function to calculate nCr (combinations)
def nCr(self, n: int, r: int) -> int:
"""
Choosing the smaller value
of r to optimize computation
"""
if r > n - r:
r = n - r
res = 1
"""
Calculate nCr using iterative
method to avoid overflow
"""
for i in range(r):
res = res * (n - i)
res = res // (i + 1)
return int(res)
# Function to generate Pascal's Triangle up to numRows rows
def pascalTriangle(self, numRows: int) -> List[List[int]]:
"""
Initialize the triangle list with numRows lists
"""
triangle = []
"""
Fill the triangle with Pascal's Triangle values
"""
for i in range(numRows):
"""
Create a new row list and
resize it to i + 1 elements
"""
row = []
for j in range(i + 1):
# Compute and store value at position (i, j)
row.append(self.nCr(i, j))
triangle.append(row)
# Return completed Pascal's Triangle
return triangle
# Main function for testing
if __name__ == "__main__":
# row number
r = 5
# col number
c = 3
# Create an instance of the Solution class
sol = Solution()
pascalTriangle = sol.generate(r)
"""
Check if column number is valid
and retrieve the element at (r, c)
"""
if r >= c > 0:
element = pascalTriangle[r - 1][c - 1]
print(f"The element at position ({r},{c}) is: {element}")
else:
"""
Print error message if column number is invalid
"""
print("Invalid column number!")
class Solution {
// Function to calculate nCr (combinations)
nCr(n, r) {
/*
Choosing the smaller value
of r to optimize computation
*/
if (r > n - r) {
r = n - r;
}
let res = 1;
/*
Calculate nCr using iterative
method to avoid overflow
*/
for (let i = 0; i < r; i++) {
res = res * (n - i);
res = Math.floor(res / (i + 1));
}
return res;
}
/* Function to generate Pascal's
Triangle up to numRows rows*/
pascalTriangle(numRows) {
/*
Initialize the triangle
array with numRows arrays
*/
let triangle = [];
/*
Fill the triangle with
Pascal's Triangle values
*/
for (let i = 0; i < numRows; i++) {
/*
Create a new row array and
resize it to i + 1 elements
*/
let row = [];
for (let j = 0; j <= i; j++) {
// Compute and store value at position (i, j)
row.push(this.nCr(i, j));
}
triangle.push(row);
}
// Return completed Pascal's Triangle
return triangle;
}
}
// Main function for testing
function main() {
// row number
let r = 5;
// col number
let c = 3;
// Create an instance of the Solution class
let sol = new Solution();
let pascalTriangle = sol.generate(r);
/*
Check if column number is valid
and retrieve the element at (r, c)
*/
if (r >= c && c > 0) {
let element = pascalTriangle[r - 1][c - 1];
console.log(`The element at position (${r},${c}) is: ${element}`);
} else {
/*
Print error message if column number is invalid
*/
console.log("Invalid column number!");
}
}
// Execute main function
main();
Given the row number n. Print the n -th row of Pascal’s triangle.
For every column from 1 to n, calculate the element n and c (where n is the given row number and c is the column number that will vary from 1 to n) using the previous method. Post this print the row.
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Function to calculate nCr (combinations)
int nCr(int n, int r) {
long long res = 1;
// Calculate nCr:
for (int i = 0; i < r; i++) {
res = res * (n - i);
res = res / (i + 1);
}
return res;
}
public:
/* Function to print Pascal's
Triangle row for given n*/
void generate(int n) {
/* Print the entire row of
Pascal's Triangle for row n:*/
for (int c = 1; c <= n; c++) {
cout << nCr(n - 1, c - 1) << " ";
}
cout << endl;
}
};
int main() {
int n = 5;
// Create an instance of the Solution class
Solution sol;
// Print Pascal's Triangle row for row n
sol.generate(n);
return 0;
}
import java.util.*;
class Solution {
// Function to calculate nCr (combinations)
private long nCr(int n, int r) {
long res = 1;
// Calculate nCr:
for (int i = 0; i < r; i++) {
res = res * (n - i);
res = res / (i + 1);
}
return res;
}
/* Function to print Pascal's
Triangle row for given n */
public void generate(int n) {
/* Print the entire row of
Pascal's Triangle for row n: */
for (int c = 1; c <= n; c++) {
System.out.print(nCr(n - 1, c - 1) + " ");
}
System.out.println();
}
public static void main(String[] args) {
int n = 5;
// Create an instance of the Solution class
Solution sol = new Solution();
// Print Pascal's Triangle row for row n
sol.generate(n);
}
}
class Solution:
# Function to calculate nCr (combinations)
def nCr(self, n: int, r: int) -> int:
"""
Calculate nCr using iterative
method to avoid overflow
"""
res = 1
for i in range(r):
res = res * (n - i)
res = res // (i + 1)
return res
""" Function to print Pascal's
Triangle row for given n """
def generate(self, n: int) -> None:
"""
Print the entire row of
Pascal's Triangle for row n:
"""
for c in range(1, n + 1):
print(self.nCr(n - 1, c - 1), end=" ")
print()
if __name__ == "__main__":
n = 5
# Create an instance of the Solution class
sol = Solution()
# Print Pascal's Triangle row for row n
sol.generate(n)
class Solution {
// Function to calculate nCr (combinations)
nCr(n, r) {
/*
Calculate nCr using iterative
method to avoid overflow
*/
let res = 1;
for (let i = 0; i < r; i++) {
res = res * (n - i);
res = Math.floor(res / (i + 1));
}
return res;
}
/* Function to print Pascal's
Triangle row for given n */
generate(n) {
/*
Print the entire row of
Pascal's Triangle for row n:
*/
for (let c = 1; c <= n; c++) {
process.stdout.write(this.nCr(n - 1, c - 1) + " ");
}
process.stdout.write("\n");
}
}
// Main execution block
let n = 5;
// Create an instance of the Solution class
let sol = new Solution();
// Print Pascal's Triangle row for row n
sol.generate(n);
Given the row number, print the Pascal’s triangle till the row number
For every column from 1 to n, calculate the element n and c (where n is the given row number and c is the column number that will vary from 1 to n) using the process used in Variety 1 of this problem.
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Function to generate a single
row of Pascal's Triangle*/
vector<int> generateRow(int row) {
long long ans = 1;
vector<int> ansRow;
/// Inserting the 1st element
ansRow.push_back(1);
// Calculate the rest of the elements
for (int col = 1; col < row; col++) {
ans = ans * (row - col);
ans = ans / col;
ansRow.push_back(ans);
}
return ansRow;
}
public:
/* Function to generate Pascal's
Triangle up to n rows*/
vector<vector<int>> pascalTriangle(int n) {
vector<vector<int>> pascalTriangle;
// Store the entire Pascal's Triangle
for (int row = 1; row <= n; row++) {
pascalTriangle.push_back(generateRow(row));
}
//return the pascalTriangle
return pascalTriangle;
}
};
int main() {
int n = 5;
Solution sol;
// Generate Pascal's Triangle with n rows
vector<vector<int>> pascalTriangle = sol.pascalTriangle(n);
// Output the Pascal's Triangle
for (auto& row : pascalTriangle) {
for (auto& element : row) {
cout << element << " ";
}
cout << endl;
}
return 0;
}
import java.util.*;
class Solution {
/* Function to generate a single
row of Pascal's Triangle*/
private List<Integer> generateRow(int row) {
long ans = 1;
List<Integer> ansRow = new ArrayList<>();
// Inserting the 1st element
ansRow.add(1);
// Calculate the rest of the elements
for (int col = 1; col < row; col++) {
ans = ans * (row - col);
ans = ans / col;
ansRow.add((int) ans);
}
return ansRow;
}
/* Function to generate Pascal's
Triangle up to n rows*/
public List<List<Integer>> pascalTriangle(int n) {
List<List<Integer>> pascalTriangle = new ArrayList<>();
// Store the entire Pascal's Triangle
for (int row = 1; row <= n; row++) {
pascalTriangle.add(generateRow(row));
}
// Return the Pascal's Triangle
return pascalTriangle;
}
public static void main(String[] args) {
int n = 5;
Solution sol = new Solution();
// Generate Pascal's Triangle with n rows
List<List<Integer>> pascalTriangle = sol.pascalTriangle(n);
// Output the Pascal's Triangle
for (List<Integer> row : pascalTriangle) {
for (int element : row) {
System.out.print(element + " ");
}
System.out.println();
}
}
}
from typing import List
class Solution:
""" Function to generate a single
row of Pascal's Triangle """
def generateRow(self, row: int) -> List[int]:
ans = 1
# Inserting the 1st element
ansRow = [1]
# Calculate the rest of the elements
for col in range(1, row):
ans = ans * (row - col)
ans = ans // col
ansRow.append(ans)
return ansRow
""" Function to generate Pascal's
Triangle up to n rows"""
def pascalTriangle(self, n: int) -> List[List[int]]:
pascalTriangle = []
# Store the entire Pascal's Triangle
for row in range(1, n + 1):
pascalTriangle.append(self.generateRow(row))
# Return the Pascal's Triangle
return pascalTriangle
if __name__ == "__main__":
n = 5
sol = Solution()
# Generate Pascal's Triangle with n rows
pascalTriangle = sol.pascalTriangle(n)
# Output the Pascal's Triangle
for row in pascalTriangle:
for element in row:
print(element, end=" ")
print()
class Solution {
/*Function to generate a single
row of Pascal's Triangle*/
generateRow(row) {
let ans = 1;
let ansRow = [];
// Inserting the 1st element
ansRow.push(1);
// Calculate the rest of the elements
for (let col = 1; col < row; col++) {
ans = ans * (row - col);
// Using Math.floor for integer division
ans = Math.floor(ans / col);
ansRow.push(ans);
}
return ansRow;
}
/* Function to generate Pascal's
Triangle up to n rows*/
pascalTriangle(n) {
let pascalTriangle = [];
// Store the entire Pascal's Triangle
for (let row = 1; row <= n; row++) {
pascalTriangle.push(this.generateRow(row));
}
return pascalTriangle;
}
}
// Main function to test the Solution class
function main() {
const n = 5;
const sol = new Solution();
// Generate Pascal's Triangle with n rows
const pascalTriangle = sol.pascalTriangle(n);
// Output the Pascal's Triangle
for (let row of pascalTriangle) {
console.log(row.join(" "));
}
}
// Calling main function to execute the code
main();
Q: How do we calculate elements in the middle of a row?
A: Each middle element is the sum of the two elements directly above it in the triangle. If the previous row is prevRow, then currRow[i] = prevRow[i - 1] + prevRow[i].
Q: How can Pascal's triangle be used to compute Fibonacci numbers?
A: The sum of elements along the diagonals of Pascal's triangle gives Fibonacci numbers.
Q: How would you compute a specific element in Pascal’s triangle without generating the entire triangle?
A: To compute the value at row r and column c (0-based indexing), use the combination formula: C(r,c)= r!/(c!×(r−c)!)
Q: How can Pascal's triangle be used in binomial expansion?
A: The n-th row of Pascal's triangle represents the coefficients of the terms in the expansion of (a+b)^n.