Minimize count of unique paths from top left to bottom right of a Matrix by placing K 1 s | Java Program to implement the above approach ; Function to return the value of Binomial Coefficient C ( n , k ) ; Since C ( n , k ) = C ( n , n - k ) ; Calculate the value of [ n * ( n - 1 ) * -- - * ( n - k + 1 ) ] / [ k * ( k - 1 ) * -- -- * 1 ] ; Function to find the minimum count of paths from top left to bottom right by placing K 1 s in the matrix ; Count of ways without 1 s ; Count of paths from starting point to mid point ; Count of paths from mid point to end point ; Driver Code
import java . util . * ; class GFG { static int ncr ( int n , int k ) { int res = 1 ; if ( k > n - k ) k = n - k ; for ( int i = 0 ; i < k ; ++ i ) { res *= ( n - i ) ; res /= ( i + 1 ) ; } return res ; } static int countPath ( int N , int M , int K ) { int answer ; if ( K >= 2 ) answer = 0 ; else if ( K == 0 ) answer = ncr ( N + M - 2 , N - 1 ) ; else { answer = ncr ( N + M - 2 , N - 1 ) ; int X = ( N - 1 ) / 2 + ( M - 1 ) / 2 ; int Y = ( N - 1 ) / 2 ; int midCount = ncr ( X , Y ) ; X = ( ( N - 1 ) - ( N - 1 ) / 2 ) + ( ( M - 1 ) - ( M - 1 ) / 2 ) ; Y = ( ( N - 1 ) - ( N - 1 ) / 2 ) ; midCount *= ncr ( X , Y ) ; answer -= midCount ; } return answer ; } public static void main ( String [ ] args ) { int N = 3 ; int M = 3 ; int K = 1 ; System . out . print ( countPath ( N , M , K ) ) ; } }