- Arrays, Hash, HashSet, Mathematical, Natural Numbers, permutation

Generate a permutation of first N natural numbers from an array of differences between adjacent elements

Generate a permutation of first N natural numbers from an array of differences between adjacent elementsGiven 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 1Explanation: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 5Approach: 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++#include using namespace std;void findPermutation(int A[], int N){    int lasEle = 0;        int perm[N];    perm[0] = 0;    for (int i = 1; i < N; i++) {                lasEle += A[i - 1];                        perm[i] = lasEle;    }            int sm = *min_element(perm, perm + N);            unordered_set st;    int mx = 0;        for (int i = 0; i < N; i++) {                perm[i] += (-sm) + 1;                mx = max(mx, perm[i]);                        st.insert(perm[i]);    }            if (mx == N and st.size() == N) {                for (int i = 0; i < N; i++) {            cout