nCr table | HackerRank Solution [Medium]

Problem

Jim is doing his discrete maths homework which requires him to repeatedly calculate nCr(n choose r) for different values of n. How will you calculate nCr values for different values of n?
Since nCr values will be large you have to calculate them modulo 109.

HackerRank Problem Link

Input

The first line contains the number of test cases T.
T lines follow each containing an integer n.

Output

For each n output the list of ⁿC₀ to ⁿC_n each separated by a single space in a new line. If the number is large, print only the last 9 digits. i.e. modulo 10⁹

Constraints

• 1 <= T <= 200
• 1 <= n < 1000

Sample Input

3
3
7
1

Sample Output

1 3 3 1 
1 7 21 35 35 21 7 1 
1 1 

Solution

Approach: Dynamic Programming
The idea is to use the dynamic programming algorithm which is used to find the Pascal’s Triangle. The solution of Pascal’s Triangle is discussed in this post.

//
//  main.cpp
//  nCr table
//
//  Created by Himanshu on 22/03/22.
//

#include<iostream>
#define MAX_SIZE 1001
#define mod 1000000000
using namespace std;
typedef long long ll;

ll pascal[MAX_SIZE][MAX_SIZE] = {0};

void precompute () {
    
    for (int i=1; i<MAX_SIZE; i++) {
        for (int j=1; j<=i; j++) {
            if (j == 1) {
                pascal[i][j] = 1;
            } else {
                pascal[i][j] = (ll)(pascal[i-1][j]+pascal[i-1][j-1])%mod;
            }
        }
    }
}

int main() {
    int T, n;
    precompute();
    
    cin>>T;
    
    while (T--) {
        cin>>n;
        
        for (int j=1; j<=(n+1); j++) {
            cout<<pascal[n+1][j]<<" ";
        }
        cout<<endl;;
    }
    
    return 0;
}

Time Complexity: O(n²)
Auxiliary Space: O(n²)