Given an array arr[] consisting of (N – 1), the task is to construct a permutation array P[] consisting of the first N Natural Numbers such that arr[i] = (P[i +1] – P[i]). If there exists no such permutation, then print “-1”.
Examples:
Input: arr[] = {-1, 2, -3, -1}
Output: 4 3 5 2 1
Explanation:
For the array {4, 3, 5, 2, 1}, the adjacent difference array of consecutive elements is {4 – 3, 5 – 3, 2 – 5, 1 – 2} = {-1, 2, -3, -1} which is the same as the array arr[].Input: arr[] = {1, 1, 1, 1}
Output: 1 2 3 4 5
Approach: The given problem can be solved by considering the first element of the permutation as 0 and then constructing a new permutation array by using the given array arr[]. After this, add the minimum element of the new array to each element to make the array elements over the range [1, N]. Follow the steps below to solve the problem:
- Initialize an array, say perm[] of size N to store the resultant permutation.
- Initialize perm[0] as 0, and also initialize a variable, say lastEle as 0.
- Iterate over the range [1, N] using the variable i, and add the value of arr[i – 1] to the element lastEle and update the value of perm[i] as lastEle.
- Initialize a variable, say minimumElement to the minimum element of the array perm[].
- Initialize a HashSet of integers st, to store all elements of the permutation. Also, initialize a variable mx as 0 to store the maximum element in the perm[] array.
- Traverse through the perm[] array and add the value of (-sm) + 1 to the value perm[i], update the value of mx as max(mx, perm[i]) and add perm[i] to st.
- After completing the above steps, if the value of mx and the size of HashSet st is N, then print the array perm[] as the resultant array. Otherwise, print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the permutation of// N integers from the given difference// array A[]void findPermutation(int A[], int N){ int lasEle = 0; // Stores the resultant permutation int perm[N]; perm[0] = 0; for (int i = 1; i < N; i++) { // Update the value of lastEle lasEle += A[i - 1]; // Initialize the value of // perm[i] perm[i] = lasEle; } // Stores the minimum element of // the array perm[] int sm = *min_element(perm, perm + N); // Stores the elements of the // permutation array perm[] unordered_set<int> st; int mx = 0; // Traverse the array for (int i = 0; i < N; i++) { // Update the value of perm[i] perm[i] += (-sm) + 1; // Update the value of mx mx = max(mx, perm[i]); // Insert the current element // in the hashset st.insert(perm[i]); } // Check if the maximum element and // the size of hashset is N or not if (mx == N and st.size() == N) { // Print the permutation for (int i = 0; i < N; i++) { cout << perm[i] << " "; } } // Otherwise print -1 else { cout << -1 << " "; }}// Driver Codeint main(){ int arr[] = { -1, 2, -3, -1 }; int N = sizeof(arr) / sizeof(arr[0]); findPermutation(arr, N + 1); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the permutation of// N integers from the given difference// array A[]static void findPermutation(int []A, int N){ int lasEle = 0; // Stores the resultant permutation int []perm = new int[N]; perm[0] = 0; for (int i = 1; i < N; i++) { // Update the value of lastEle lasEle += A[i - 1]; // Initialize the value of // perm[i] perm[i] = lasEle; } // Stores the minimum element of // the array perm[] int sm = perm[0]; //Loop through the array for (int i = 0; i < perm.length; i++) { //Compare elements of array with min if(perm[i] <sm) sm = perm[i]; } // Stores the elements of the // permutation array perm[] Set<Integer> st = new HashSet<Integer>(); int mx = 0; // Traverse the array for (int i = 0; i < N; i++) { // Update the value of perm[i] perm[i] += (-sm) + 1; // Update the value of mx mx = Math.max(mx, perm[i]); // Insert the current element // in the hashset st.add(perm[i]); } // Check if the maximum element and // the size of hashset is N or not if (mx == N && st.size() == N) { // Print the permutation for (int i = 0; i < N; i++) { System.out.print(perm[i]+" "); } } // Otherwise print -1 else { System.out.print(-1); }}// Driver Codepublic static void main(String args[]){ int arr[] = { -1, 2, -3, -1 }; int N = arr.length; findPermutation(arr, N + 1);}}// This code is contributed by SURENDRA_GANGWAR. |
Python3
# Python program for the above approach# Function to find the permutation of# N integers from the given difference# array A[]def findPermutation(A, N): lasEle = 0 # Stores the resultant permutation perm = [0]*N perm[0] = 0 for i in range(1,N): # Update the value of lastEle lasEle += A[i - 1] # Initialize the value of # perm[i] perm[i] = lasEle # Stores the minimum element of # the array perm[] sm = min(perm) # Stores the elements of the # permutation array perm[] st = {} mx = 0 # Traverse the array for i in range(N): # Update the value of perm[i] perm[i] += (-sm) + 1 # Update the value of mx mx = max(mx, perm[i]) # Insert the current element # in the hashset st[perm[i]] = 1 # Check if the maximum element and # the size of hashset is N or not if (mx == N and len(st) == N): # Print the permutation for i in range(N): print(perm[i],end=" ") # Otherwise print -1 else: print(-1,end=" ")# Driver Codeif __name__ == '__main__': arr = [-1, 2, -3, -1] N = len(arr) findPermutation(arr, N + 1)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Linq;using System.Collections.Generic;class GFG {// Function to find the permutation of// N integers from the given difference// array A[]static void findPermutation(int[] A, int N){ int lasEle = 0; // Stores the resultant permutation int[] perm = new int[N]; perm[0] = 0; for (int i = 1; i < N; i++) { // Update the value of lastEle lasEle += A[i - 1]; // Initialize the value of // perm[i] perm[i] = lasEle; } // Stores the minimum element of // the array perm[] int sm = perm.Min(); // Stores the elements of the // permutation array perm[] List<int> st = new List<int>(); int mx = 0; // Traverse the array for (int i = 0; i < N; i++) { // Update the value of perm[i] perm[i] += (-sm) + 1; // Update the value of mx mx = Math.Max(mx, perm[i]); // Insert the current element // in the hashset st.Add(perm[i]); } // Check if the maximum element and // the size of hashset is N or not if (mx == N && st.Count == N) { // Print the permutation for (int i = 0; i < N; i++) { Console.Write(perm[i] + " "); } } // Otherwise print -1 else { Console.Write(-1 + " "); }} // Driver Code static void Main() { int[] arr= { -1, 2, -3, -1 }; int N = arr.Length; findPermutation(arr, N + 1); }}// This code is contributed by sanjoy_62. |
Javascript
<script>// JavaScript program for the above approach// Function to find the permutation of// N integers from the given difference// array A[]function findPermutation(A, N) { let lasEle = 0; // Stores the resultant permutation let perm = new Array(N); perm[0] = 0; for (let i = 1; i < N; i++) { // Update the value of lastEle lasEle += A[i - 1]; // Initialize the value of // perm[i] perm[i] = lasEle; } // Stores the minimum element of // the array perm[] let temp = [...perm]; let sm = temp.sort((a, b) => a - b)[0] // Stores the elements of the // permutation array perm[] let st = new Set(); let mx = 0; // Traverse the array for (let i = 0; i < N; i++) { // Update the value of perm[i] perm[i] += (-sm) + 1; // Update the value of mx mx = Math.max(mx, perm[i]); // Insert the current element // in the hashset st.add(perm[i]); } // Check if the maximum element and // the size of hashset is N or not if (mx == N && st.size == N) { // Print the permutation for (let i of perm) { document.write(i + " ") } } // Otherwise print -1 else { document.write(-1 + " "); }}// Driver Codelet arr = [-1, 2, -3, -1];let N = arr.lengthfindPermutation(arr, N + 1);</script> |
Output:
4 3 5 2 1
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!
