pascals_triangle_improved.py

# using factorial, reduced the time complexity
# of program from O(2^N) to O(N)


deffactorial(n):
ifn<2:
return1
else:
returnn*factorial(n-1)


defcomputeCoefficient(col, row):
returnfactorial(row) // (factorial(col) *factorial(row-col))


# Recusrive method to create the series
defcomputePascal(col, row):
ifcol==roworcol==0:
return1
else:
returncomputeCoefficient(col, row)


# Method to create the triangle for `N` row
defprintTriangle(num):
forrinrange(num):
forcinrange(r+1):
print(str(computePascal(c, r)), end=" ")
print("\n")


printTriangle(10)
"""
Output:
1 

1 1 

1 2 1 

1 3 3 1 

1 4 6 4 1 

1 5 10 10 5 1 

1 6 15 20 15 6 1 

1 7 21 35 35 21 7 1 

1 8 28 56 70 56 28 8 1 

1 9 36 84 126 126 84 36 9 1 
"""