Genere una permutación de los primeros N números naturales a partir de una array de diferencias entre elementos adyacentes

Dada una array arr[] que consta de (N – 1) , la tarea es construir una array de permutación P[] que consta de los primeros N números naturales tales que arr[i] = (P[i +1] – P[i ]) . Si no existe tal permutación, imprima “-1” .

Ejemplos:

Entrada: arr[] = {-1, 2, -3, -1}
Salida: 4 3 5 2 1
Explicación:
Para la array {4, 3, 5, 2, 1}, la array de diferencia adyacente de elementos consecutivos es {4 – 3, 5 – 3, 2 – 5, 1 – 2} = {-1, 2, -3, -1} que es lo mismo que el arreglo arr[].

Entrada: arr[] = {1, 1, 1, 1}
Salida: 1 2 3 4 5

Enfoque: el problema dado se puede resolver considerando el primer elemento de la permutación como 0 y luego construyendo una nueva array de permutación utilizando la array dada arr[]. Después de esto, agregue el elemento mínimo de la nueva array a cada elemento para hacer que los elementos de la array estén sobre el rango [1, N] . Siga los pasos a continuación para resolver el problema:

• Inicialice una array, digamos perm[] de tamaño N para almacenar la permutación resultante.
• Inicialice perm[0] como 0 , y también inicialice una variable, digamos lastEle como 0 .
• Itere sobre el rango [1, N] usando la variable i, y agregue el valor de arr[i – 1] al elemento lastEle y actualice el valor de perm[i] como lastEle .
• Inicializa una variable, digamos minimalElement al elemento mínimo de la array perm[] .
• Inicialice un HashSet de enteros st , para almacenar todos los elementos de la permutación. Además, inicialice una variable mx como 0 para almacenar el elemento máximo en la array perm[] .
• Recorra la array perm[] y agregue el valor de (-sm) + 1 al valor perm[i] , actualice el valor de mx como max(mx, perm[i]) y agregue perm[i] a st .
• Después de completar los pasos anteriores, si el valor de mx y el tamaño de HashSet st es N , imprima la array perm[] como la array resultante. De lo contrario, imprima -1 .

A continuación se muestra la implementación del enfoque anterior:
 

// 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 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.

# 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# 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.

<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>

4 3 5 2 1

Complejidad temporal: O(N)
Espacio auxiliar: O(N)