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

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 Code
int 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 approach
import 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 Code
public 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 Code
if __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 approach
using 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 Code
 
let arr = [-1, 2, -3, -1];
let N = arr.length
findPermutation(arr, N + 1);
 
</script>

Output:

4 3 5 2 1

Time Complexity: O(N)
Auxiliary Space: O(N)

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Maximum element present in the array after performing queries to add K to range of indices [L, R]
Minimize sum of numbers required to convert an array into a permutation of first N natural numbers
Probability of obtaining pairs from two arrays such that element from the first array is smaller than that of the second array
Split an array into subarrays with maximum Bitwise XOR of their respective Bitwise OR values
Minimize sum of points assigned to distinct elements present in an array

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	9