Minimum changes required to make a Catalan Sequence | Java implementation of the approach ; To store first N Catalan numbers ; Function to find first n Catalan numbers ; Initialize first two values in table ; Filong 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
class GFG1 { static int MAX = 100000 ; static long catalan [ ] = new long [ MAX ] ; static void catalanDP ( long 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 ] ; } } } static int CatalanSequence ( int arr [ ] , int n ) { catalanDP ( n ) ; HashSet < Integer > s = new HashSet < Integer > ( ) ; int a = 1 , b = 1 ; int c ; s . add ( a ) ; if ( n >= 2 ) { s . add ( b ) ; } for ( int i = 2 ; i < n ; i ++ ) { s . add ( ( int ) catalan [ i ] ) ; } for ( int i = 0 ; i < n ; i ++ ) { if ( s . contains ( arr [ i ] ) ) { s . remove ( arr [ i ] ) ; } } return s . size ( ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 1 , 2 , 5 , 41 } ; int n = arr . length ; System . out . print ( CatalanSequence ( arr , n ) ) ; } }