Lexicographically Kth smallest way to reach given coordinate from origin | CPP Program to find 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 . ; Driven Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int factorial ( int a , int b ) { int res = 1 ; for ( int i = 1 ; i <= ( a + b ) ; i ++ ) res = res * i ; for ( int i = 1 ; i <= a ; i ++ ) res = res / i ; for ( int i = 1 ; i <= b ; i ++ ) res = res / i ; return res ; } void Ksmallest ( int x , int y , int k ) { if ( x == 0 && y == 0 ) return ; else if ( x == 0 ) { y -- ; cout << " V " ; Ksmallest ( x , y , k ) ; } else if ( y == 0 ) { x -- ; cout << " H " ; Ksmallest ( x , y , k ) ; } else { if ( factorial ( x - 1 , y ) > k ) { cout << " H " ; Ksmallest ( x - 1 , y , k ) ; } else { cout << " V " ; Ksmallest ( x , y - 1 , k - factorial ( x - 1 , y ) ) ; } } } int main ( ) { int x = 2 , y = 2 , k = 2 ; Ksmallest ( x , y , k ) ; return 0 ; }