CODEWITHSUNDEEP
arrayscombinationspascals-triangle
Dillydill123
Dillydill123

Reputation: 693

Retrieving a value from pascals triangle

I have a one dimensional array that is holding values of pascal's triangle counting the numbers from left to right.

int pascal[10] = { 1, 1, 1, 1, 2, 1, 1, 3, 3, 1 };

How can I use this to quickly find the combination of two numbers?

e.g. to find 3 choose 1, I would look in the array to find the answer 3. How can I correctly calculate the index that I need to look at?

If I wanted to continue building Pascal's triangle, how can I use this array to build it without doing tree recursion? Something like a recurrence relation

Upvotes: 0

Views: 254

Answers (1)

rbm
rbm

Reputation: 3253

If you insist on using the array rather than calculating it via formula then you can use following (C# example):

int Choose_N_over_K(int N, int K)
{
    int[] pascal  = new[] { 1, 1, 1, 1, 2, 1,1, 3, 3, 1, 1,4,6,4,1};    
    var index = (N * (N + 1) / 2 +  K  );
    return (pascal[index]);
}


void Main()
{
        Console.WriteLine(Choose_N_over_K(4,2));
}

Giving (for the example of 4 over 2):

6

We simply calculate the index in the array based on the fact that every row in triangle has one more element than the previous row and we know how to sum numbers 1..N:

// 0: 1  start index 0
// 1: 1 1  start index 1
// 2: 1 2 1  start index 3 
// 3: 1 3 3 1 start index 6
// 4: 1 4 6 4 1 start index 10

Upvotes: 1

Related Questions