Encuentre la array de permutación de la array de suma acumulativa

Dado un arreglo arr[] de N elementos donde cada arreglo[i] es la suma acumulada del subarreglo P[0…i] de otro arreglo P[] donde P es la permutación de los enteros de 1 a N. La tarea es encontrar la array P[] , si no existe tal P, imprima -1 .
Ejemplos: 
 

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

Acercarse: 
 

• El primer elemento de la array acumulativa debe ser el primer elemento de la array de permutación y el elemento en la i- ^ésima posición será arr[i] – arr[i – 1] ya que arr[] es la array de suma acumulativa de la array de permutación.
• Por lo tanto, encuentre la array de la array de suma acumulativa y luego marque la ocurrencia de cada elemento del 1 al N que está presente en la array generada.
• Si algún elemento aparece más de una vez, la permutación no es válida; de lo contrario, imprima la permutación.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the valid permutation
void getPermutation(int a[], int n)
{
 
    // Find the array from the cumulative sum
    vector<int> ans(n);
    ans[0] = a[0];
    for (int i = 1; i < n; i++)
        ans[i] = a[i] - a[i - 1];
 
    // To mark the occurrence of an element
    bool present[n + 1] = { false };
    for (int i = 0; i < ans.size(); i++) {
 
        // If current element has already
        // been seen previously
        if (present[ans[i]]) {
            cout << "-1";
            return;
        }
 
        // Mark the current element's occurrence
        else
            present[ans[i]] = true;
    }
 
    // Print the required permutation
    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";
}
 
// Driver code
int main()
{
    int a[] = { 2, 3, 6 };
    int n = sizeof(a) / sizeof(a[0]);
 
    getPermutation(a, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to find the valid permutation
static void getPermutation(int a[], int n)
{
 
    // Find the array from the cumulative sum
    int []ans = new int[n];
    ans[0] = a[0];
    for (int i = 1; i < n; i++)
        ans[i] = a[i] - a[i - 1];
 
    // To mark the occurrence of an element
    boolean []present = new boolean[n + 1];
    for (int i = 0; i < ans.length; i++)
    {
 
        // If current element has already
        // been seen previously
        if (present[ans[i]])
        {
            System.out.print("-1");
            return;
        }
 
        // Mark the current element's occurrence
        else
            present[ans[i]] = true;
    }
 
    // Print the required permutation
    for (int i = 0; i < n; i++)
        System.out.print(ans[i] + " ");
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 2, 3, 6 };
    int n = a.length;
 
    getPermutation(a, n);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of the approach
 
# Function to find the valid permutation
def getPermutation(a, n) :
 
    # Find the array from the cumulative sum
    ans = [0] * n;
    ans[0] = a[0];
    for i in range(1, n) :
        ans[i] = a[i] - a[i - 1];
 
    # To mark the occurrence of an element
    present = [0] * (n + 1);
     
    for i in range(n) :
 
        # If current element has already
        # been seen previously
        if (present[ans[i]]) :
            print("-1", end = "");
            return;
 
        # Mark the current element's occurrence
        else :
            present[ans[i]] = True;
 
    # Print the required permutation
    for i in range(n) :
        print(ans[i], end = " ");
 
# Driver code
if __name__ == "__main__" :
 
    a = [ 2, 3, 6 ];
    n = len(a);
 
    getPermutation(a, n);
     
# This code is contributed by AnkitRai01

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to find the valid permutation
static void getPermutation(int [] a, int n)
{
 
    // Find the array from the cumulative sum
    List<int> ans = new List<int>();
    ans.Add(a[0]);
    for (int i = 1; i < n; i++)
        ans.Add(a[i] - a[i - 1]);
 
    // To mark the occurrence of an element
    List<int> present = new List<int>();
 
    for (int i = 0; i < n+1; i++)
        present.Add(0);
 
    for (int i = 0; i < ans.Count; i++)
    {
 
        // If current element has already
        // been seen previously
        if (present[ans[i]] == 1)
        {
            Console.Write("-1");
            return;
        }
 
        // Mark the current element's occurrence
        else
            present[ans[i]] = 1;
    }
 
    // Print the required permutation
    for (int i = 0; i < n; i++)
        Console.Write(ans[i] + " ");
}
 
// Driver code
static public void Main()
{
    int[] a = { 2,3,6};
    int n = a.Length;
    getPermutation(a, n);
}
}
 
// This code is contributed by mohit kumar 29

<script>
 
// Javascript implementation of the approach
 
// Function to find the valid permutation
function getPermutation(a, n)
{
 
    // Find the array from the cumulative sum
    var ans = Array(n);
    ans[0] = a[0];
    for (var i = 1; i < n; i++)
        ans[i] = a[i] - a[i - 1];
 
    // To mark the occurrence of an element
    var present = Array(n+1).fill(false);
    for (var i = 0; i < ans.length; i++) {
 
        // If current element has already
        // been seen previously
        if (present[ans[i]]) {
            document.write( "-1");
            return;
        }
 
        // Mark the current element's occurrence
        else
            present[ans[i]] = true;
    }
 
    // Print the required permutation
    for (var i = 0; i < n; i++)
        document.write( ans[i] + " ");
}
 
// Driver code
var a = [2, 3, 6];
var n = a.length;
getPermutation(a, n);
 
// This code is contributed by rrrtnx.
</script>

2 1 3

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)