Given an array arr containing N positive integers, the task is to check if the given array can be dissociated into two permutations or not and print the permutations if possible. 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, 2 }, N = 7
Output: {1 2 5 3 4}, {1 2}
Input: arr[] = {2, 1, 1, 3}, N = 4
Output: Not possible
Approach:
- First of all, we need to check if the array is the concatenation of two permutations.It is explained in this article.
- If so, find the largest element of the array, say x.
- If the elements at indices [0, x-1] and [x, n-1] form two valid permutations, print them.
- Otherwise, print the elements at indices [0, n -1 – x] and [n – x, n – 1] as the two valid permutations.
Below is the implementation of the above approach:
C++
// C++ program to print two// permutations from a given sequence#include <bits/stdc++.h>using namespace std;// Function to check if the sequence is// concatenation of two permutations or notbool 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;}// Function to print the// two permutationsvoid printPermutations(int arr[], int n, int l1, int l2){ // Print the first permutation for (int i = 0; i < l1; i++) { cout << arr[i] << " "; } cout << endl; // Print the second permutation for (int i = l1; i < n; i++) { cout << arr[i] << " "; }}// Function to find the two permutations// from the given sequencevoid findPermutations(int arr[], int n){ // If the sequence is not a // concatenation of two permutations if (!checkPermutation(arr, n)) { cout << "Not Possible"; return; } int l1 = 0, l2 = 0; // Find the largest element in the // array and set the lengths of the // permutations accordingly l1 = *max_element(arr, arr + n); l2 = n - l1; set<int> s1, s2; for (int i = 0; i < l1; i++) s1.insert(arr[i]); for (int i = l1; i < n; i++) s2.insert(arr[i]); if (s1.size() == l1 && s2.size() == l2) printPermutations(arr, n, l1, l2); else { swap(l1, l2); printPermutations(arr, n, l1, l2); }}// Driver codeint main(){ int arr[] = { 2, 1, 3, 4, 5, 6, 7, 8, 9, 1, 10, 2 }; int n = sizeof(arr) / sizeof(int); findPermutations(arr, n); return 0;} |
Java
// Java program to print two// permutations from a given sequenceimport java.util.*;class GFG{ // Function to check if the sequence is// concatenation of two permutations or notstatic boolean checkPermutation(int arr[], int n){ // Computing the sum of all the // elements in the array long 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 long lsum = prefix[i]; // Sum of remaining n-i-1 elements long rsum = sum - prefix[i]; // Lengths of the 2 permutations 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;} // Function to print the// two permutationsstatic void printPermutations(int arr[], int n, int l1, int l2){ // Print the first permutation for (int i = 0; i < l1; i++) { System.out.print(arr[i]+ " "); } System.out.println(); // Print the second permutation for (int i = l1; i < n; i++) { System.out.print(arr[i]+ " "); }} // Function to find the two permutations// from the given sequencestatic void findPermutations(int arr[], int n){ // If the sequence is not a // concatenation of two permutations if (!checkPermutation(arr, n)) { System.out.print("Not Possible"); return; } int l1 = 0, l2 = 0; // Find the largest element in the // array and set the lengths of the // permutations accordingly 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); }} // Driver codepublic 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);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to print two# permutations from a given sequence# Function to check if the sequence is# concatenation of two permutations or notdef 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 for i in range(n+1)] prefix[0] = arr[0] for i in range(1,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# Function to print the# two permutationsdef printPermutations(arr,n,l1,l2): # Print the first permutation for i in range(l1): print(arr[i],end = " ") print("\n",end = ""); # Print the second permutation for i in range(l1, n, 1): print(arr[i], end = " ")# Function to find the two permutations# from the given sequencedef findPermutations(arr,n): # If the sequence is not a # concatenation of two permutations if (checkPermutation(arr, n) == False): print("Not Possible") return l1 = 0 l2 = 0 # Find the largest element in the # array and set the lengths of the # permutations accordingly l1 = max(arr) l2 = n - l1 s1 = set() s2 = set() for i in range(l1): s1.add(arr[i]) for i in range(l1,n): s2.add(arr[i]) if (len(s1) == l1 and len(s2) == l2): printPermutations(arr, n, l1, l2) else: temp = l1 l1 = l2 l2 = temp printPermutations(arr, n, l1, l2)# Driver codeif __name__ == '__main__': arr = [2, 1, 3, 4, 5,6, 7, 8, 9, 1,10, 2] n = len(arr) findPermutations(arr, n)# This code is contributed by Surendra_Gangwar |
C#
// C# program to print two// permutations from a given sequenceusing System;using System.Linq;using System.Collections.Generic;class GFG{ // Function to check if the sequence is// concatenation of two permutations or notstatic bool checkPermutation(int []arr, int n){ // Computing the sum of all the // elements in the array long 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 long lsum = prefix[i]; // Sum of remaining n-i-1 elements long rsum = sum - prefix[i]; // Lengths of the 2 permutations 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;} // Function to print the// two permutationsstatic void printPermutations(int []arr, int n, int l1, int l2){ // Print the first permutation for (int i = 0; i < l1; i++) { Console.Write(arr[i]+ " "); } Console.WriteLine(); // Print the second permutation for (int i = l1; i < n; i++) { Console.Write(arr[i]+ " "); }} // Function to find the two permutations// from the given sequencestatic void findPermutations(int []arr, int n){ // If the sequence is not a // concatenation of two permutations if (!checkPermutation(arr, n)) { Console.Write("Not Possible"); return; } int l1 = 0, l2 = 0; // Find the largest element in the // array and set the lengths of the // permutations accordingly l1 = arr.Max(); l2 = n - l1; HashSet<int> s1 = new HashSet<int>(), s2 = new HashSet<int>(); for (int i = 0; i < l1; i++) s1.Add(arr[i]); for (int i = l1; i < n; i++) s2.Add(arr[i]); if (s1.Count == l1 && s2.Count == l2) printPermutations(arr, n, l1, l2); else { l1 = l1+l2; l2 = l1-l2; l1 = l1-l2; printPermutations(arr, n, l1, l2); }} // Driver codepublic 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);}}// This code contributed by Rajput-Ji |
Javascript
// Python3 program to print two// permutations from a given sequence// Function to check if the sequence is// concatenation of two permutations or notfunction checkPermutation(arr, n){ // Computing the sum of all the // elements in the array let sum = 0 for (var i = 0; i < n; i++) sum += arr[i] // Computing the prefix sum // for all the elements in the array let prefix = new Array(n + 1) prefix[0] = arr[0] for (var i = 1; i < n; i++) prefix[i] = prefix[i - 1] + arr[i] // Iterating through the i // from lengths 1 to n-1 for (var 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 let 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}// Function to print the// two permutationsfunction printPermutations(arr,n,l1,l2){ // Print the first permutation for (var i = 0; i < l1; i++) process.stdout.write(arr[i] + " ") process.stdout.write("\n") // Print the second permutation for (var i = l1; i < n; i++) process.stdout.write(arr[i] + " ")} // Function to find the two permutations// from the given sequencefunction findPermutations(arr,n){ // If the sequence is not a // concatenation of two permutations if (checkPermutation(arr, n) == false) { console.log("Not Possible") return } let l1 = 0 let l2 = 0 // Find the largest element in the // array and set the lengths of the // permutations accordingly l1 = Math.max.apply(null, arr) l2 = n - l1 let s1 = new Set() let s2 = new Set() for (var i = 0; i < l1; i++) s1.add(arr[i]) for (var i = l1; i < n; i++) s2.add(arr[i]) if ((s1).size == l1 && (s2).size == l2) printPermutations(arr, n, l1, l2) else { let temp = l1 l1 = l2 l2 = temp printPermutations(arr, n, l1, l2) }}// Driver codelet arr = [2, 1, 3, 4, 5,6, 7, 8, 9, 1,10, 2]let n = arr.lengthfindPermutations(arr, n)// This code is contributed by phasing17 |
Output:
2 1 3 4 5 6 7 8 9 1 10 2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
