Count non decreasing subarrays of size N from N Natural numbers | C ++ program to count non decreasing subarrays of size N from N Natural numbers ; Returns value of Binomial Coefficient C ( n , k ) ; Since nC0 is 1 ; Compute next row of pascal triangle using the previous row ; Function to find the count of required subarrays ; The required count is the binomial coefficient as explained in the approach above ; Driver Function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int binomialCoeff ( int n , int k ) { int C [ k + 1 ] ; memset ( C , 0 , sizeof ( C ) ) ; C [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = min ( i , k ) ; j > 0 ; j -- ) C [ j ] = C [ j ] + C [ j - 1 ] ; } return C [ k ] ; } int count_of_subarrays ( int N ) { int count = binomialCoeff ( 2 * N - 1 , N ) ; return count ; } int main ( ) { int N = 3 ; cout << count_of_subarrays ( N ) << " STRNEWLINE " ; }