Check if a Sequence is a concatenation of two permutations | Function to Check if a given sequence is a concatenation of two permutations or not ; Computing the sum of all the elements in the array ; Computing the prefix sum for all the elements in the array ; Iterating through the i from lengths 1 to n - 1 ; Sum of first i + 1 elements ; Sum of remaining n - i - 1 elements ; Lengths of the 2 permutations ; Checking if the sums satisfy the formula or not ; Driver code
def checkPermutation ( arr , n ) : NEW_LINE INDENT sum = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += arr [ i ] ; NEW_LINE DEDENT prefix = [ 0 ] * ( n + 1 ) ; NEW_LINE prefix [ 0 ] = arr [ 0 ] ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT prefix [ i ] = prefix [ i - 1 ] + arr [ i ] ; NEW_LINE DEDENT for i in range ( n - 1 ) : NEW_LINE INDENT lsum = prefix [ i ] ; NEW_LINE rsum = sum - prefix [ i ] ; NEW_LINE l_len = i + 1 NEW_LINE r_len = n - i - 1 ; NEW_LINE if ( ( ( 2 * lsum ) == ( l_len * ( l_len + 1 ) ) ) and ( ( 2 * rsum ) == ( r_len * ( r_len + 1 ) ) ) ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT DEDENT return False ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 5 , 3 , 4 , 1 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE if ( checkPermutation ( arr , n ) ) : NEW_LINE INDENT print ( " Yes " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) ; NEW_LINE DEDENT DEDENT