Encuentre la permutación p de la array q tal que q[i] = p[i+1] – p[i]

Dada una array Q[] de longitud N , la tarea es encontrar la permutación P[] de números enteros del rango [1, N + 1] tal que Q[i] = P[i + 1] – P[i] para todos los válidos i . Si no es posible, imprima -1 .

Ejemplos: 

Entrada: Q[] = {-2, 1} 
Salida: 3 1 2 
q[0] = p[1] – p[0] = 1 – 3 = -2 
q[1] = p[2] – p[ 1] = 2 – 1 = 1

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

Entrada: Q[] = {-1, 2, 2} 
Salida: -1 
 

Enfoque: 
Vamos,  

P[0] = x entonces P[1] = P[0] + (P[1] – P[0]) = x + Q[0] 
y, P[2] = P[0] + (P[ 1] – P[0]) + (P[2] – P[1]) = x + Q[0] + Q[1] . 
 

Similarmente,  

P[n] = x + Q[0] + Q[1] + Q[2] + ….. + Q[N – 1] . 
 

Significa que la secuencia p’ = 0, Q[1], Q[1] + Q[2], ….., + Q[1] + Q[2] + Q[3] + ….. + Q [N – 1] es la permutación requerida si agregamos x a cada elemento.
Para encontrar el valor de x , encuentre una i tal que p'[i] sea mínima.
Como p'[i] + x es el valor mínimo en la serie, entonces debe ser igual a 1 ya que la serie puede tener valores de [1, N] . 
Entonces x = 1 – p'[i] .

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 return the minimum
// value of x from the given array q
int Get_Minimum(vector<int> q)
{
    int minimum = 0;
    int sum = 0;
    for(int i = 0; i < q.size() - 1; i++)
    {
        sum += q[i];
        if (sum < minimum)
            minimum = sum;
    }
    return minimum;
}
 
// Function to return the required permutation
vector<int> Find_Permutation(vector<int> q, int n)
{
    vector<int> p(n, 0);
    int min_value = Get_Minimum(q);
 
    // Set the value of p[0] i.e. x = p[0]
    p[0] = 1 - min_value;
 
    // Iterate over array q[]
    for (int i = 0; i < n - 1; i++)
        p[i + 1] = p[i] + q[i];
 
    bool okay = true;
 
    // Check if formed permutation
    // is correct or not
    for (int i = 0; i < n; i++)
    {
        if (p[i] < 1 or p[i] > n)
            okay = false;
        set<int> w(p.begin(), p.end());
        if (w.size() != n)
            okay = false;
    }
 
    // Return the permutation p
    if (okay)
        return p;
    else
        return {-1};
}
 
// Driver code
int main()
{
    vector<int> q = {-2, 1};
    int n = q.size() + 1;
    cout << "[ ";
    for (int i:Find_Permutation(q, n))
        cout << i << " ";
    cout << "]";    
}
 
// This code is contributed by Mohit Kumar

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the minimum
// value of x from the given array q
static int Get_Minimum(int [] q)
{
    int minimum = 0;
    int sum = 0;
    for(int i = 0; i < q.length - 1; i++)
    {
        sum += q[i];
        if (sum < minimum)
            minimum = sum;
    }
    return minimum;
}
 
// Function to return the required permutation
static int [] Find_Permutation(int [] q, int n)
{
    int [] p = new int[n];
    int min_value = Get_Minimum(q);
 
    // Set the value of p[0] i.e. x = p[0]
    p[0] = 1 - min_value;
 
    // Iterate over array q[]
    for (int i = 0; i < n - 1; i++)
        p[i + 1] = p[i] + q[i];
 
    boolean okay = true;
 
    // Check if formed permutation
    // is correct or not
    for (int i = 0; i < n; i++)
    {
        if (p[i] < 1 || p[i] > n)
            okay = false;
        Set<Integer> w = new HashSet<>();
        if (w.size() != n)
            okay = true;
    }
 
    // Return the permutation p
    if (okay)
        return p;
    else
        return new int []{-1};
}
 
// Driver code
public static void main(String args[])
{
    int []q = {-2, 1};
    int n = q.length + 1;
    System.out.print("[ ");
    for (int i:Find_Permutation(q, n))
        System.out.print(i + " ");
    System.out.print("]");
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
 
# Function to return the minimum
# value of x from the given array q
def Get_Minimum(q):
    minimum = 0
    sum = 0
    for i in range(n - 1):
        sum += q[i]
        if sum < minimum:
            minimum = sum
    return minimum
 
# Function to return the
# required permutation
def Find_Permutation(q):
    p = [0] * n
    min_value = Get_Minimum(q)
 
    # Set the value of p[0]
    # i.e. x = p[0]
    p[0]= 1 - min_value
 
    # Iterate over array q[]
    for i in range(n - 1):
        p[i + 1] = p[i] + q[i]
 
    okay = True
 
    # Check if formed permutation
    # is correct or not
    for i in range(n):
        if p[i] < 1 or p[i] > n:
            okay = False
    if len(set(p)) != n:
        okay = False
 
    # Return the permutation p
    if okay:
        return p
    else:
        return -1
 
# Driver code
if __name__=="__main__":
    q = [-2, 1]
    n = len(q) + 1
    print(Find_Permutation(q))

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to return the minimum
// value of x from the given array q
static int Get_Minimum(int [] q)
{
    int minimum = 0;
    int sum = 0;
    for(int i = 0; i < q.Length - 1; i++)
    {
        sum += q[i];
        if (sum < minimum)
            minimum = sum;
    }
    return minimum;
}
 
// Function to return the required permutation
static int [] Find_Permutation(int [] q, int n)
{
    int [] p = new int[n];
    int min_value = Get_Minimum(q);
 
    // Set the value of p[0] i.e. x = p[0]
    p[0] = 1 - min_value;
 
    // Iterate over array q[]
    for (int i = 0; i < n - 1; i++)
        p[i + 1] = p[i] + q[i];
 
    bool okay = true;
 
    // Check if formed permutation
    // is correct or not
    for (int i = 0; i < n; i++)
    {
        if (p[i] < 1 || p[i] > n)
            okay = false;
        HashSet<int> w = new HashSet<int>();
        if (w.Count != n)
            okay = true;
    }
 
    // Return the permutation p
    if (okay)
        return p;
    else
        return new int []{-1};
}
 
// Driver code
public static void Main(String []args)
{
    int []q = {-2, 1};
    int n = q.Length + 1;
    Console.Write("[ ");
    foreach (int i in Find_Permutation(q, n))
        Console.Write(i + " ");
    Console.Write("]");
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript implementation of the approach
 
// Function to return the minimum
// value of x from the given array q
function Get_Minimum(q)
{
    let minimum = 0;
    let sum = 0;
    for(let i = 0; i < q.length - 1; i++)
    {
        sum += q[i];
        if (sum < minimum)
            minimum = sum;
    }
    return minimum;
}
 
// Function to return the required permutation   
function Find_Permutation(q, n)
{
    let p = new Array(n);
    let min_value = Get_Minimum(q);
   
    // Set the value of p[0] i.e. x = p[0]
    p[0] = 1 - min_value;
   
    // Iterate over array q[]
    for(let i = 0; i < n - 1; i++)
        p[i + 1] = p[i] + q[i];
   
    let okay = true;
   
    // Check if formed permutation
    // is correct or not
    for(let i = 0; i < n; i++)
    {
        if (p[i] < 1 || p[i] > n)
            okay = false;
             
        let w = new Set();
        if (w.size != n)
            okay = true;
    }
   
    // Return the permutation p
    if (okay)
        return p;
    else
        return new [-1];
}
 
// Driver code
let q = [ -2, 1 ];
let n = q.length + 1;
document.write("[ ");
 
let temp = Find_Permutation(q, n);
for(let i = 0; i < temp.length; i++)
    document.write(temp[i] + " ");
     
document.write("]");
 
// This code is contributed by patel2127
 
</script>

[3, 1, 2]

Complejidad de Tiempo : O(n ² )
Espacio Auxiliar : O(n)