Count all N | Function to prthe count of arrays satisfying given condition ; First element of array is set as 1 ; Since the first element of arr is 1 , the second element can 't be 1 ; Traverse the remaining indices ; If arr [ i ] = 1 ; If arr [ i ] a 1 ; Since last element needs to be 1 ; Driver Code ; Stores the count of arrays where arr [ 0 ] = arr [ N - 1 ] = 1 ; Since arr [ 0 ] and arr [ N - 1 ] can be any number from 1 to M ; Pranswer
def totalArrays ( N , M ) : NEW_LINE INDENT end_with_one = [ 0 ] * ( N + 1 ) ; NEW_LINE end_not_with_one = [ 0 ] * ( N + 1 ) ; NEW_LINE end_with_one [ 0 ] = 1 ; NEW_LINE end_not_with_one [ 0 ] = 0 ; NEW_LINE end_with_one [ 1 ] = 0 ; NEW_LINE end_not_with_one [ 1 ] = M - 1 ; NEW_LINE for i in range ( 2 , N ) : NEW_LINE INDENT end_with_one [ i ] = end_not_with_one [ i - 1 ] ; NEW_LINE end_not_with_one [ i ] = end_with_one [ i - 1 ] * ( M - 1 ) + end_not_with_one [ i - 1 ] * ( M - 2 ) ; NEW_LINE DEDENT return end_with_one [ N - 1 ] ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 ; NEW_LINE M = 3 ; NEW_LINE temp = totalArrays ( N , M ) ; NEW_LINE ans = M * temp ; NEW_LINE print ( ans ) ; NEW_LINE DEDENT