# Pascal's Triangle generator

What’s Pascal’s Triangle? That’s what it is (Wikipedia has all the theory, if you need).

The thing I wrote here is a generator of the *n-th row* of the triangle, that doesn’t use more then the memory needed to store the solution. Instead of allocating a *Triangular Matrix*, and building every row based on the one above, solution is *built in place*.

## How does it work

The result is generated *“filling the row from right to left”*. I start initiating the element on the right hand side to `'1'`

. Then, I run something like:

```
init result[0.. requested_row]
result[requested_row-1] = 1
for i = 2 -> requested_row do:
for j = requested_row-i -> requested_row-1 do:
result[j] = result[j] + result[j+1]
endfor
endfor
```

Clearly this is nothing special. Just a little trick to avoid to use a triangular matrix. Memory is not cheap, you know! ;-)

```
#include <stdio.h>
#include <stdlib.h>
void print_row(unsigned long long* row, unsigned int size) {
static unsigned int j;
for ( j = 0; j < size; ++j ) { printf("%llu ", row[j]); }
printf("\n");
}
unsigned long long* pascal_triangle_line(unsigned int pascal_row){
static unsigned int i, j;
unsigned long long* result = NULL;
result = (unsigned long long*)calloc(pascal_row, sizeof(unsigned long long));
if ( NULL != result ) {
result[pascal_row-1] = 1; // First element on the right is always '1'
for ( i = 2; i <= pascal_row; ++i ) {
#ifdef DEBUG
print_row(result, pascal_row);
#endif
for ( j = pascal_row-i; j < pascal_row-1; ++j ) {
result[j] += result[j+1]; // Calculate the 'j'-th element
#ifdef VERBOSE
printf("(row: %d, element: %d) => %llu\n", i, j, result[j]);
#endif
}
}
}
return (result);
}
int main(int argc, char** argv)
{
unsigned int input;
unsigned long long* result = NULL;
// Check the Input
if ( argc == 2 ) input = atoi(argv[1]); else return (EXIT_FAILURE);
// Calculate the required line
result = pascal_triangle_line(input);
// Print result
if ( NULL != result ) {
printf("RESULT ROW:\n");
print_row(result, input);
return (EXIT_SUCCESS);
}
return (EXIT_FAILURE);
}
```

Complexity in time: O(n^{2}/2). After all, the complexity is a constant operation O(1), multiplied by the number of elements in the Triangular Matrix: n^{2} elements divided by 2. BUT bear in mind that O(n^{2}/2) = O(n^{2}). So, **it’s more correct to say that the complexity is quadratic**.

Of course, if instead you need the whole triangle (not just an arbitrary row) you will have to store it somewhere, so this solution wouldn’t work for you as it is.