Minimum changes required to make a Catalan Sequence | PHP 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
< ? php $ MAX = 1000 ; $ catalan = array_fill ( 0 , $ MAX , 0 ) ; function catalanDP ( $ n ) { global $ catalan ; $ catalan [ 0 ] = $ catalan [ 1 ] = 1 ; for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) { $ catalan [ $ i ] = 0 ; for ( $ j = 0 ; $ j < $ i ; $ j ++ ) { $ catalan [ $ i ] += $ catalan [ $ j ] * $ catalan [ $ i - $ j - 1 ] ; } } } function CatalanSequence ( $ arr , $ n ) { global $ catalan ; catalanDP ( $ n ) ; $ s = array ( ) ; $ a = $ b = 1 ; array_push ( $ s , $ a ) ; if ( $ n >= 2 ) { array_push ( $ s , $ b ) ; } for ( $ i = 2 ; $ i < $ n ; $ i ++ ) { array_push ( $ s , $ catalan [ $ i ] ) ; } $ s = array_unique ( $ s ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { if ( in_array ( $ arr [ $ i ] , $ s ) ) { unset ( $ s [ array_search ( $ arr [ $ i ] , $ s ) ] ) ; } } return count ( $ s ) ; } $ arr = array ( 1 , 1 , 2 , 5 , 41 ) ; $ n = count ( $ arr ) ; print ( CatalanSequence ( $ arr , $ n ) ) ; ? >