text: Minimum changes required to make a Catalan Sequence | C ++ implementation of the approach ; To store first N Catalan numbers ; Function to find first n Catalan numbers ; Initialize first two values in table ; Fill entries in catalan [ ] using recursive formula ; Function to return the minimum changes required ; Find first n Catalan Numbers ; a and b are first two Catalan Sequence numbers ; Insert first n catalan elements to set ; If catalan element is present in the array then remove it from set ; Return the remaining number of elements in the set ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100000 NEW_LINE #define ll  long long int NEW_LINE ll catalan [ MAX ] ; void catalanDP ( ll n ) { catalan [ 0 ] = catalan [ 1 ] = 1 ; for ( int i = 2 ; i <= n ; i ++ ) { catalan [ i ] = 0 ; for ( int j = 0 ; j < i ; j ++ ) catalan [ i ] += catalan [ j ] * catalan [ i - j - 1 ] ; } } int CatalanSequence ( int arr [ ] , int n ) { catalanDP ( n ) ; unordered_multiset < int > s ; int a = 1 , b = 1 ; int c ; s . insert ( a ) ; if ( n >= 2 ) s . insert ( b ) ; for ( int i = 2 ; i < n ; i ++ ) { s . insert ( catalan [ i ] ) ; } unordered_multiset < int > :: iterator it ; for ( int i = 0 ; i < n ; i ++ ) { it = s . find ( arr [ i ] ) ; if ( it != s . end ( ) ) s . erase ( it ) ; } return s . size ( ) ; } int main ( ) { int arr [ ] = { 1 , 1 , 2 , 5 , 41 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << CatalanSequence ( arr , n ) ; return 0 ; }