Minimize count of unique paths from top left to bottom right of a Matrix by placing K 1 s | 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 poto mid point ; Count of paths from mid poto end point ; Driver Code
def ncr ( n , k ) : NEW_LINE INDENT res = 1 NEW_LINE if ( k > n - k ) : NEW_LINE INDENT k = n - k NEW_LINE DEDENT for i in range ( k ) : NEW_LINE INDENT res *= ( n - i ) NEW_LINE res //= ( i + 1 ) NEW_LINE DEDENT return res NEW_LINE DEDENT def countPath ( N , M , K ) : NEW_LINE INDENT answer = 0 NEW_LINE if ( K >= 2 ) : NEW_LINE INDENT answer = 0 NEW_LINE DEDENT elif ( K == 0 ) : NEW_LINE INDENT answer = ncr ( N + M - 2 , N - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT answer = ncr ( N + M - 2 , N - 1 ) NEW_LINE X = ( N - 1 ) // 2 + ( M - 1 ) // 2 NEW_LINE Y = ( N - 1 ) // 2 NEW_LINE midCount = ncr ( X , Y ) NEW_LINE X = ( ( N - 1 ) - ( N - 1 ) // 2 ) + NEW_LINE INDENT ( ( M - 1 ) - ( M - 1 ) // 2 ) NEW_LINE DEDENT Y = ( ( N - 1 ) - ( N - 1 ) // 2 ) NEW_LINE midCount *= ncr ( X , Y ) NEW_LINE answer -= midCount NEW_LINE DEDENT return answer NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 NEW_LINE M = 3 NEW_LINE K = 1 NEW_LINE print ( countPath ( N , M , K ) ) NEW_LINE DEDENT