HiveBrain v1.2.0
Get Started
← Back to all entries
snippetpythonMinor

How can this function be faster? Solving for a row of Pascal's triangle

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thiscansolvingpascalfunctionfastertriangleforhowrow

Problem

I saw a posting on Hacker News this morning that was ranting about people not being able to solve an interview question. I thought I would give it a shot, but I would like to know how my attempt could be improved.

def get_pascal_row(n):
    """
    Returns the nth row of Pascal's Triangle for a given n. Uses
    Gray's algorithm.
    """
    if n == 0: return []
    n -= 1
    row = [1]
    for i in xrange(1,n+1):
        row.append(row[-1] * n/i)
        n -= 1
    return row

Solution

You can memoize the rows you have already computed previously.

Alternatively, you could compute it in closed form using the binomial coefficients:

Start looking in scipy.special.binom.

Context

StackExchange Code Review Q#20850, answer score: 3

Revisions (0)

No revisions yet.