Check if a Sequence is a concatenation of two permutations | C ++ program to check if a given sequence is a concatenation of two permutations or not ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool checkPermutation ( int arr [ ] , int n ) { long long sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; long long prefix [ n + 1 ] = { 0 } ; prefix [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) prefix [ i ] = prefix [ i - 1 ] + arr [ i ] ; for ( int i = 0 ; i < n - 1 ; i ++ ) { long long lsum = prefix [ i ] ; long long rsum = sum - prefix [ i ] ; long long l_len = i + 1 , r_len = n - i - 1 ; if ( ( ( 2 * lsum ) == ( l_len * ( l_len + 1 ) ) ) && ( ( 2 * rsum ) == ( r_len * ( r_len + 1 ) ) ) ) return true ; } return false ; } int main ( ) { int arr [ ] = { 1 , 2 , 5 , 3 , 4 , 1 , 2 } ; int n = sizeof ( arr ) / sizeof ( int ) ; if ( checkPermutation ( arr , n ) ) cout << " Yes STRNEWLINE " ; else cout << " No STRNEWLINE " ; return 0 ; }