#include <stdio.h>

unsigned long ncr(int n, int r) {

static unsigned long table[256][256] = {0};

if(r == 0 || n == r) {

return table[n][r] = 1;

}

if(r == 1) {

return table[n][r] = n;

}

if(r > n / 2) {

return table[n][r] = ncr(n, n - r);

}

return table[n][r] = table[n - 1][r - 1] + table[n - 1][r];

}

void printPascal(int n) {

int numSpaces = n;

int i, j;

for(i = 0; i <= n; ++i) {

for(j = 0; j < numSpaces; ++j)

printf(" ");

for(j = 0; j <= i; ++j)

printf("%lu ", ncr(i, j));

printf("\n");

numSpaces--;

}

}

int main() {

int n;

scanf("%d", &n);

printPascal(n);

return 0;

}

### Like this:

Like Loading...

*Related*

You are a genius.1.Two reverse sorted arrays A and B have been given.such that size of A is m and size of B is nYou need to find the k th largest sum (a+b) where a is taken from A and b is taken from B. such that k < m*nIt can be done in O(n*n) but i believe it can be done in a very efficient way. I heard someone say there is a paper from SODA. It's possible to solve it in O(N), however, it requires very complex algorithm. I am wondering if you can come up with an NlogN algorithm first then try O(N). These two problems have been very hot interview problems from Google, however, not many people can solve it very efficiently yet. I believe you can do it after I read many posts on your site.2.Given a N*N Matrix. All rows are sorted, and all columns are sorted.Find the Kth Largest element of the matrix.

Answer to answer 2.#include#include#include#includeusing namespace std ;#define SIZE 4int matrix[SIZE][SIZE] = { {1, 2, 6, 10}, {3, 4, 7, 13}, {5, 9, 11, 14}, {8, 12, 15, 16} };typedef struct node { int x, y ; int val ; bool operator < (const node& obj) const { return (val > obj.val) ; }}node ;int findKthMin (int mat[SIZE][SIZE], int k) { int count = 0 ; node n ; int row, col ; priority_queue elements ; n.x = 0 ; n.y = 0 ; n.val = mat[0][0] ; mat[0][0] = INT_MAX ; elements.push (n) ; while (count <= k) { n = elements.top() ; elements.pop () ; printf ( "%d\n", n.val ) ; count ++ ; node temp ; if ( n.x < SIZE-1 ) { temp.x = n.x + 1 ; temp.y = n.y ; if ( mat[temp.x][temp.y] != INT_MAX ) { temp.val = mat[temp.x][temp.y] ; mat[temp.x][temp.y] = INT_MAX ; elements.push (temp) ; } } if ( n.y < SIZE-1 ) { temp.x = n.x ; temp.y = n.y + 1 ; if ( mat[temp.x][temp.y] != INT_MAX ) { temp.val = mat[temp.x][temp.y] ; mat[temp.x][temp.y] = INT_MAX ; elements.push ( temp ) ; } } }}int main () { int k ; printf ( "\nEnter the k (0 index) :\t" ) ; scanf ( "%d", &k ) ; findKthMin (matrix, k) ; return 0 ;}