Given an array arr containing positive integers, the task is to check if the given array arr is a concatenation of two permutations or not. A sequence of M integers is called a permutation if it contains all integers from 1 to M exactly once.
Examples:
Input: arr[] = {1, 2, 5, 3, 4, 1, 1}
Output: No
Explanation:
Given array contains 1 thrice. The first 5 elements form a permutation of length 5, but the remaining 2 elements do not form a permutation.
Input: arr[] = {1, 2, 5, 3, 4, 1, 2}
Output: Yes
Explanation:
Given array arr[] = {1, 2, 5, 3, 4} + {1, 2}
The first 5 elements form a permutation of length 5 and the remaining 2 elements form a permutation of length 2.
Approach:
- Traverse through the given array and calculate the sum of all the elements.
- Form a prefix array containing the prefix sum.
- Now, for each index in range [1, N)
- Check if the elements, from start to current index, form a permutation, using the below condition:
Sum of K elements = Sum of K natural numbers where K is the current index
- Then check the remaining elements forms a permutation.
- If yes, then we print/return Yes.
Below is the implementation of the above approach:
C++
// C++ program to check if a given sequence // is a concatenation of two permutations or not #include <bits/stdc++.h> using namespace std; // Function to Check if a given sequence // is a concatenation of two permutations or not bool checkPermutation( int arr[], int n) { // Computing the sum of all the // elements in the array long long sum = 0; for ( int i = 0; i < n; i++) sum += arr[i]; // Computing the prefix sum // for all the elements in the array long long prefix[n + 1] = { 0 }; prefix[0] = arr[0]; for ( int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + arr[i]; // Iterating through the i // from lengths 1 to n-1 for ( int i = 0; i < n - 1; i++) { // Sum of first i+1 elements long long lsum = prefix[i]; // Sum of remaining n-i-1 elements long long rsum = sum - prefix[i]; // Lengths of the 2 permutations long long l_len = i + 1, r_len = n - i - 1; // Checking if the sums // satisfy the formula or not if (((2 * lsum) == (l_len * (l_len + 1))) && ((2 * rsum) == (r_len * (r_len + 1)))) return true ; } return false ; } // Driver code int main() { int arr[] = { 1, 2, 5, 3, 4, 1, 2 }; int n = sizeof (arr) / sizeof ( int ); if (checkPermutation(arr, n)) cout << "Yes\n" ; else cout << "No\n" ; return 0; } |
Java
// Java program to check if a given sequence // is a concatenation of two permutations or not import java.util.*; class GFG{ // Function to Check if a given sequence // is a concatenation of two permutations or not static boolean checkPermutation( int []arr, int n) { // Computing the sum of all the // elements in the array int sum = 0 ; for ( int i = 0 ; i < n; i++) sum += arr[i]; // Computing the prefix sum // for all the elements in the array int []prefix = new int [n + 1 ]; Arrays.fill(prefix, 0 ); prefix[ 0 ] = arr[ 0 ]; for ( int i = 1 ; i < n; i++) prefix[i] = prefix[i - 1 ] + arr[i]; // Iterating through the i // from lengths 1 to n-1 for ( int i = 0 ; i < n - 1 ; i++) { // Sum of first i+1 elements int lsum = prefix[i]; // Sum of remaining n-i-1 elements int rsum = sum - prefix[i]; // Lengths of the 2 permutations int l_len = i + 1 , r_len = n - i - 1 ; // Checking if the sums // satisfy the formula or not if ((( 2 * lsum) == (l_len * (l_len + 1 ))) && (( 2 * rsum) == (r_len * (r_len + 1 )))) return true ; } return false ; } // Driver code public static void main(String args[]) { int []arr = { 1 , 2 , 5 , 3 , 4 , 1 , 2 }; int n = arr.length; if (checkPermutation(arr, n)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Surendra_Gangwar |
Python3
# Python 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 def checkPermutation(arr, n): # Computing the sum of all the # elements in the array sum = 0 ; for i in range (n): sum + = arr[i]; # Computing the prefix sum # for all the elements in the array prefix = [ 0 ] * (n + 1 ); prefix[ 0 ] = arr[ 0 ]; for i in range (n): prefix[i] = prefix[i - 1 ] + arr[i]; # Iterating through the i # from lengths 1 to n-1 for i in range (n - 1 ): # Sum of first i+1 elements lsum = prefix[i]; # Sum of remaining n-i-1 elements rsum = sum - prefix[i]; # Lengths of the 2 permutations l_len = i + 1 r_len = n - i - 1 ; # Checking if the sums # satisfy the formula or not if ((( 2 * lsum) = = (l_len * (l_len + 1 ))) and (( 2 * rsum) = = (r_len * (r_len + 1 )))): return True ; return False ; # Driver code if __name__ = = '__main__' : arr = [ 1 , 2 , 5 , 3 , 4 , 1 , 2 ] n = len (arr) if (checkPermutation(arr, n)): print ( "Yes" ); else : print ( "No" ); # This code is contributed by Princi Singh |
C#
// C# program to check if a given sequence // is a concatenation of two permutations or not using System; class GFG{ // Function to Check if a given sequence // is a concatenation of two permutations or not static bool checkPermutation( int []arr, int n) { // Computing the sum of all the // elements in the array int sum = 0; for ( int i = 0; i < n; i++) sum += arr[i]; // Computing the prefix sum // for all the elements in the array int []prefix = new int [n + 1]; prefix[0] = arr[0]; for ( int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + arr[i]; // Iterating through the i // from lengths 1 to n-1 for ( int i = 0; i < n - 1; i++) { // Sum of first i+1 elements int lsum = prefix[i]; // Sum of remaining n-i-1 elements int rsum = sum - prefix[i]; // Lengths of the 2 permutations int l_len = i + 1, r_len = n - i - 1; // Checking if the sums // satisfy the formula or not if (((2 * lsum) == (l_len * (l_len + 1))) && ((2 * rsum) == (r_len * (r_len + 1)))) return true ; } return false ; } // Driver code public static void Main(String []args) { int []arr = { 1, 2, 5, 3, 4, 1, 2 }; int n = arr.Length; if (checkPermutation(arr, n)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript 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 function checkPermutation(arr, n) { // Computing the sum of all the // elements in the array let sum = 0; for (let i = 0; i < n; i++) sum += arr[i]; // Computing the prefix sum // for all the elements in the array let prefix = Array.from({length: n+1}, (_, i) => 0); prefix[0] = arr[0]; for (let i = 1; i < n; i++) prefix[i] = prefix[i - 1] + arr[i]; // Iterating through the i // from lengths 1 to n-1 for (let i = 0; i < n - 1; i++) { // Sum of first i+1 elements let lsum = prefix[i]; // Sum of remaining n-i-1 elements let rsum = sum - prefix[i]; // Lengths of the 2 permutations let l_len = i + 1, r_len = n - i - 1; // Checking if the sums // satisfy the formula or not if (((2 * lsum) == (l_len * (l_len + 1))) && ((2 * rsum) == (r_len * (r_len + 1)))) return true ; } return false ; } // Driver Code let arr = [ 1, 2, 5, 3, 4, 1, 2 ]; let n = arr.length; if (checkPermutation(arr, n)) document.write( "Yes" ); else document.write( "No" ); </script> |
Yes
Time Complexity: O(n)
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!