printing pascal triangle

#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;
}
Advertisements

2 thoughts on “printing pascal triangle

  1. 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.

  2. 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 ;}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s