Home
C++ and Python to Compute the Pascal Triangle
Tags:, , , , ,

C++ and Python to Compute the Pascal Triangle

April 4, 2015 No Comments algorithms, c / c++, dynamic programming, math, python

Given an index k, return the k-th row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].
Could you optimize your algorithm to use only O(k) extra space?

C++ O(n^2) to Compute the Pascal Triangle

It is easy to know that each number in the triangle equals to the sum of the two numbers of its shoulder if there are any. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> r;
        if (rowIndex == 0) {
            r.push_back(1);
            return r;
        }
        r.resize(rowIndex + 1);
        r[0] = 1;
        r[1] = 1;
        for (int i = 0; i < rowIndex - 1; i ++) {
            for (int j = rowIndex; j > 0; j --) {
                r[j] += r[j - 1];
            }
        }
        return r;
    }
};
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> r;
        if (rowIndex == 0) {
            r.push_back(1);
            return r;
        }
        r.resize(rowIndex + 1);
        r[0] = 1;
        r[1] = 1;
        for (int i = 0; i < rowIndex - 1; i ++) {
            for (int j = rowIndex; j > 0; j --) {
                r[j] += r[j - 1];
            }
        }
        return r;
    }
};

We don’t need to store two dimension pascal triangles as when we calculate the k-th row all we need is (k-1)-th row of numbers. We allocate rowIndex + 1 elements in the vector and set the first two elements to both ones. rowIndex = 0 is the special case so we need to return a vector that contains a single element 1 and return it.

Then for next rowIndex – 1 iterations, we sum from right to the left interactively. The C++ submission is fast.

c-plus-plus-pascal-triangle C++ and Python to Compute the Pascal Triangle algorithms c / c++ dynamic programming math python

c-plus-plus-pascal-triangle

The Python equivalence looks simpler:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    # @return a list of integers
    def getRow(self, rowIndex):
        if rowIndex == 0:
            return [1]
        r = [0] * (rowIndex + 1)
        r[0] = 1
        r[1] = 1
        for i in range(rowIndex - 1):
            for j in range(rowIndex, 0, -1):
                r[j] = r[j] + r[j - 1]
        return r
class Solution:
    # @return a list of integers
    def getRow(self, rowIndex):
        if rowIndex == 0:
            return [1]
        r = [0] * (rowIndex + 1)
        r[0] = 1
        r[1] = 1
        for i in range(rowIndex - 1):
            for j in range(rowIndex, 0, -1):
                r[j] = r[j] + r[j - 1]
        return r

But python is generally slower in terms of performance.

python-submission C++ and Python to Compute the Pascal Triangle algorithms c / c++ dynamic programming math python

python-submission

Compute the Pacal Triangle in C++ O(n) time O(k) space

Each line of Pascal’s Triangle is a full set of Combination number based on k . 

1

comb(k,p) = k! /( p! *(k-p)!) = comb(k,k-p)
comb(k,p) = k! /( p! *(k-p)!) = comb(k,k-p)

if p < k-p

1

comb(k,p) = comb(k,p-1) * (k-p+1) / p
comb(k,p) = comb(k,p-1) * (k-p+1) / p

Because :

1

comb(k,p) = [ k * (k-1) * (k-2) *... (k-p+1)] / [1 * 2 * 3 *...(p)]
comb(k,p) = [ k * (k-1) * (k-2) *... (k-p+1)] / [1 * 2 * 3 *...(p)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans(rowIndex + 1, 1);
        int small = rowIndex / 2;
        long comb = 1;
        int j = 1;
        for (int i = rowIndex; i >= small; i--){
            comb *= i;
            comb /= j;
            j ++;
            ans[i-1] = (int)comb;
            ans[j-1] = (int)comb;
        }
        return ans;
    }
};
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans(rowIndex + 1, 1);
        int small = rowIndex / 2;
        long comb = 1;
        int j = 1;
        for (int i = rowIndex; i >= small; i--){
            comb *= i;
            comb /= j;
            j ++;
            ans[i-1] = (int)comb;
            ans[j-1] = (int)comb;
        }
        return ans;
    }
};

This runs approximately two times faster (2ms) than the above O(n^2) solution. A similar solution gives also 2ms (calculate the first half of the array)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> result(rowIndex + 1, 1);
        long current_multiplier = 1;
        for (int n = 1; n <= rowIndex / 2; ++n) {
            current_multiplier *= (rowIndex - n + 1);
            current_multiplier /= n;
            result[n] = current_multiplier;
        }
        for (int n = rowIndex / 2 + 1; n < rowIndex; ++n) {
            result[n] = result[rowIndex - n];
        }
        return result;
    }
};
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> result(rowIndex + 1, 1);
        long current_multiplier = 1;
        for (int n = 1; n <= rowIndex / 2; ++n) {
            current_multiplier *= (rowIndex - n + 1);
            current_multiplier /= n;
            result[n] = current_multiplier;
        }
        for (int n = rowIndex / 2 + 1; n < rowIndex; ++n) {
            result[n] = result[rowIndex - n];
        }
        return result;
    }
};

To compute the N-th row of a Pascal Triangle: You can use Dynamic Programming algorithm: Compute the Nth Row of a Pascal’s Triangle using Dynamic Programming Algorithm

Pascal Triangle Implementations:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
778 words
Last Post: How to Search Twits with Pictures/Images using PHP?
Next Post: Linux Bash Coding Exercise - Get the Tenth Line of File

The Permanent URL is: C++ and Python to Compute the Pascal Triangle

Related posts:

  1. Recursion and Two Pointer Algorithms to Determine Four Sum Given a list of integers nums and an integer k, return whether there are four...
  2. Duplicate a MySQL table – Copy Table / Duplicate Database / PHP Script Suppose if you want to copy a Table to another, this can be done in...
  3. Introduction to programming – C Exercise – Circuit Consider the following circuit; The step response of this circuit may be expressed as follows;...
  4. Two Pointer with Sliding Window Algorithm to Compute the Longest Substring with At Most K Distinct Characters Given a string, find the length of the longest substring T that contains at most...
  5. Teaching Kids Programming – Sum of Distinct Positive Factorial Numbers via Depth First Search Algorithm Teaching Kids Programming: Videos on Data Structures and Algorithms Given a positive integer n, return...
  6. Algorithms to Shift a 2D Grid/Matrix In-Place Given a 2D grid of size n * m and an integer k. You need...
  7. Compute the Maximum Product of Three Numbers in an Array Given an array of integers – find out the maximum product of the tree numbers...
  8. Test Javascript On/Off in PHP via POST Javascript is almost enabled in modern browsers. However, at some legacy devices or some particular...

Leave a Reply