Pascals Triangle method not working after 14th row

Question

I've been developing a method for outputting Pascal's Triangle as a list. For example: outputting PascalsTriangle(4) will return a list containing: (1 1 1 1 2 1 1 3 3 1).

The problem lies when trying to output PascalsTriangle(14) and above, as it will not display a correct value.

For the 14th row it will give: 1 4 24 88 221 399 532 532 399 221 88 24 4 1 which is wrong.

The correct values for the 14th row are: 1 13 78 186 715 1287 1716 1716 1287 715 186 78 13 1

Note: All Pascal's Triangle values before the 14th row are correct (to my knowledge).

After the 14th row it proceeds to output numbers going even into the negatives which shouldn't even be possible.

Here is the code:

using System;
using System.Collections.Generic;
namespace PascalsTriangle
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Enter size of triangle: ");
            List<int> number = PascalsTriangle(int.Parse(Console.ReadLine()));
            number.ForEach(Console.WriteLine);
        }
        // formula for pascals triangle: n!/k!(n - k)!
        // where ! means factorial and 
        // where n = row and k = position in row.
        public static List<int> PascalsTriangle(int n)
        {
            List<int> triangle = new List<int>();
            int temp = 0;
            for (int i = 0; i < n; i++)
            {
                    for (int x = 0; x <= i; x++)
                    {
                        if (x == 0 || x == i)
                        {
                            triangle.Add(1);
                        }
                        else
                        {
                            temp = (factorial(i)) / (factorial(x) * factorial(i - x));
                            triangle.Add(temp);
                        }
                    }
            }
            return triangle;
        }
        public static int factorial(int number)
        {
            if (number == 0)
            {
                return 1;
            }
            int factorial = number;
            while (number > 1)
            {
                factorial *= --number;
            }
            return factorial;
        }
    }
}

It seems like the problem lies where the numbers in the list start to become 4-digit values as that is when the code starts to stop working as intended.

Any help will be greatly appreciated :)

You are getting integer overflow. Change `int` to `long` in your app and it will output the correct values. — Ian Kemp, Dec 09 '20 at 12:43
Another more robust fix might be writing another method which calculates factorial(a)/factorial(b), considering that that's just Π_{i = b+1}^a i, this would avoid some overflows — blenderfreaky, Dec 09 '20 at 12:46

blenderfreaky · Accepted Answer · 2020-12-09T13:11:57.350

3

Your calculation of temp overflows. You could use a bigger data-type (like long or BigInteger), but Factorials grow quickly, so it might be better to use a different method of calculating temp.

What you're calculating is the binomial coefficient, see this StackOverflow answer on how to implement it. Then just use that in place of (factorial(i)) / (factorial(x) * factorial(i - x)).

edited Dec 09 '20 at 13:11

answered Dec 09 '20 at 13:02

blenderfreaky

738
7
26

Pascals Triangle method not working after 14th row

1 Answers1