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
def factorial ( a , b ) : NEW_LINE INDENT res = 1 NEW_LINE for i in range ( 1 , a + b + 1 ) : NEW_LINE INDENT res = res * i NEW_LINE DEDENT for i in range ( 1 , a + 1 ) : NEW_LINE INDENT res = res // i NEW_LINE DEDENT for i in range ( 1 , b + 1 ) : NEW_LINE INDENT res = res // i NEW_LINE DEDENT return res NEW_LINE DEDENT def Ksmallest ( x , y , k ) : NEW_LINE INDENT if x == 0 and y == 0 : NEW_LINE INDENT return NEW_LINE DEDENT elif x == 0 : NEW_LINE INDENT y -= 1 NEW_LINE print ( " V " , end = " " ) NEW_LINE Ksmallest ( x , y , k ) NEW_LINE DEDENT elif y == 0 : NEW_LINE INDENT x -= 1 NEW_LINE print ( " H " , end = " " ) NEW_LINE Ksmallest ( x , y , k ) NEW_LINE DEDENT else : NEW_LINE INDENT if factorial ( x - 1 , y ) > k : NEW_LINE INDENT print ( " H " , end = " " ) NEW_LINE Ksmallest ( x - 1 , y , k ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " V " , end = " " ) NEW_LINE Ksmallest ( x , y - 1 , k - factorial ( x - 1 , y ) ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT x , y , k = 2 , 2 , 2 NEW_LINE Ksmallest ( x , y , k ) NEW_LINE DEDENT