Print the two possible permutations from a given sequence | Java program to print two permutations from a given sequence ; Function to check if the sequence is 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 ; Function to print the two permutations ; Print the first permutation ; Print the second permutation ; Function to find the two permutations from the given sequence ; If the sequence is not a concatenation of two permutations ; Find the largest element in the array and set the lengths of the permutations accordingly ; Driver code
import java . util . * ; class GFG { static boolean checkPermutation ( int arr [ ] , int n ) { long sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; int [ ] prefix = new int [ n + 1 ] ; 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 lsum = prefix [ i ] ; long rsum = sum - prefix [ i ] ; 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 ; } static void printPermutations ( int arr [ ] , int n , int l1 , int l2 ) { for ( int i = 0 ; i < l1 ; i ++ ) { System . out . print ( arr [ i ] + " ▁ " ) ; } System . out . println ( ) ; for ( int i = l1 ; i < n ; i ++ ) { System . out . print ( arr [ i ] + " ▁ " ) ; } } static void findPermutations ( int arr [ ] , int n ) { if ( ! checkPermutation ( arr , n ) ) { System . out . print ( " Not ▁ Possible " ) ; return ; } int l1 = 0 , l2 = 0 ; l1 = Arrays . stream ( arr ) . max ( ) . getAsInt ( ) ; l2 = n - l1 ; HashSet < Integer > s1 = new HashSet < Integer > ( ) , s2 = new HashSet < Integer > ( ) ; for ( int i = 0 ; i < l1 ; i ++ ) s1 . add ( arr [ i ] ) ; for ( int i = l1 ; i < n ; i ++ ) s2 . add ( arr [ i ] ) ; if ( s1 . size ( ) == l1 && s2 . size ( ) == l2 ) printPermutations ( arr , n , l1 , l2 ) ; else { l1 = l1 + l2 ; l2 = l1 - l2 ; l1 = l1 - l2 ; printPermutations ( arr , n , l1 , l2 ) ; } } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 1 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 1 , 10 , 2 } ; int n = arr . length ; findPermutations ( arr , n ) ; } }