Lexicographically Kth smallest way to reach given coordinate from origin | Return ( a + b ) ! / a ! b ! ; finding ( a + b ) ! ; finding ( a + b ) ! / a ! ; finding ( a + b ) ! / b ! ; Return the Kth smallest way to reach given coordinate from origin ; if at origin ; if on y - axis ; decrement y . ; Move vertical ; recursive call to take next step . ; If on x - axis ; decrement x . ; Move horizontal . ; recursive call to take next step . ; If x + y C x is greater than K ; Move Horizontal ; recursive call to take next step . ; Move vertical ; recursive call to take next step . ; Driver Code
< ? php function factorial ( $ a , $ b ) { $ res = 1 ; for ( $ i = 1 ; $ i <= ( $ a + $ b ) ; $ i ++ ) $ res = $ res * $ i ; for ( $ i = 1 ; $ i <= $ a ; $ i ++ ) $ res = $ res / $ i ; for ( $ i = 1 ; $ i <= $ b ; $ i ++ ) $ res = $ res / $ i ; return $ res ; } function Ksmallest ( $ x , $ y , $ k ) { if ( $ x == 0 && $ y == 0 ) return ; else if ( $ x == 0 ) { $ y -- ; echo ( " V " ) ; Ksmallest ( $ x , $ y , $ k ) ; } else if ( $ y == 0 ) { $ x -- ; echo ( " H " ) ; Ksmallest ( $ x , $ y , $ k ) ; } else { if ( factorial ( $ x - 1 , $ y ) > $ k ) { echo ( " H " ) ; Ksmallest ( $ x - 1 , $ y , $ k ) ; } else { echo ( " V " ) ; Ksmallest ( $ x , $ y - 1 , $ k - factorial ( $ x - 1 , $ y ) ) ; } } } $ x = 2 ; $ y = 2 ; $ k = 2 ; Ksmallest ( $ x , $ y , $ k ) ; ? >