Encuentre la array original de la array de suma de prefijos dada

Dado el prefijo sum array presum[] de un array. La tarea es encontrar la array original cuyo prefijo sum es presum[] . 

Ejemplos: 

Entrada:  presum[] = {5, 7, 10, 11, 18}
Salida: [5, 2, 3, 1, 7]
Explicación: array original {5, 2, 3, 1, 7} 
Prefijo suma array = { 5, 5+2, 5+2+3, 5+2+3+1, 5+2+3+1+7} = {5, 7, 10, 11, 18}
Cada elemento de la array original se reemplaza por la suma del prefijo del índice actual.

Entrada: presum[] = {45, 57, 63, 78, 89, 97}
Salida: [45, 12, 6, 15, 11, 8] 

Planteamiento: Este problema se puede resolver con base en la siguiente observación.

Dado el prefijo sum array presum[] y supongamos que el array original es arr[] y el tamaño es N .
La array presum[] se calcula de la siguiente manera:

• presum[0] = arr[0]
• presum[i] = arr[0] + arr[1] + . . . + arr[i] para todos los i en el rango [1, N-1]

Entonces, presum[i] = arr[0] + arr[i] + . . . + arr[i-1] + arr[i] 
                       = presum[i-1] + arr[i]
Por tanto, arr[i] = presum[i] – presum[i-1]. para todo i en el rango [1, N-1] y,
arr[0] = presum[0]

Siga los pasos que se mencionan a continuación para resolver el problema:

1. Atraviese la array presum[] comenzando desde el principio de la array.
2. Si índice (i) = 0 entonces arr[i] = presum[i] .
3. De lo contrario, arr[i] = presum[i] – presum[i-1] .

A continuación se muestra el código para la implementación anterior: 

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Finds and prints the elements of
// the original array
void DecodeOriginalArray(int presum[], int N)
{
    // Calculating elements of original array
    for (int i = N - 1; i > 0; i--)
        presum[i] = presum[i] - presum[i - 1];
 
    // Displaying elements of original array
    for (int i = 0; i < N; i++)
        cout << presum[i] << " ";
}
 
// Driver program to test above
int main()
{
    int presum[] = { 45, 57, 63, 78, 89, 97 };
    int N = sizeof(presum) / sizeof(presum[0]);
 
    // Function Call
    DecodeOriginalArray(presum, N);
    return 0;
}

// Java implementation for the above approach
class GFG {
 
  // Finds and prints the elements of
  // the original array
  static void DecodeOriginalArray(int presum[], int N)
  {
 
    // Calculating elements of original array
    for (int i = N - 1; i > 0; i--)
      presum[i] = presum[i] - presum[i - 1];
 
    // Displaying elements of original array
    for (int i = 0; i < N; i++)
      System.out.print(presum[i] + " ");
  }
 
  // Driver program to test above
  public static void main(String args[])
  {
    int presum[] = { 45, 57, 63, 78, 89, 97 };
    int N = presum.length;
 
    // Function Call
    DecodeOriginalArray(presum, N);
  }
}
 
// This code is contributed by saurabh_jaiswal.

# Python code for the above approach
 
# Finds and prints the elements of
# the original array
def DecodeOriginalArray(presum, N):
 
    # Calculating elements of original array
    for i in range(N - 1, 0, -1):
        presum[i] = presum[i] - presum[i - 1];
 
    # Displaying elements of original array
    for i in range(N):
        print(presum[i], end= " ");
 
# Driver program to test above
presum = [45, 57, 63, 78, 89, 97];
N = len(presum)
 
# Function Call
DecodeOriginalArray(presum, N);
 
# This code is contributed by Saurabh Jaiswal

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Finds and prints the elements of
  // the original array
  static void DecodeOriginalArray(int[ ] presum, int N)
  {
 
    // Calculating elements of original array
    for (int i = N - 1; i > 0; i--)
      presum[i] = presum[i] - presum[i - 1];
 
    // Displaying elements of original array
    for (int i = 0; i < N; i++)
      Console.WriteLine(presum[i]);
  }
 
  // Driver code
  public static void Main(string[] args)
  {
 
    int[] presum = { 45, 57, 63, 78, 89, 97 };
    int N = presum.Length;
 
    // Function Call
    DecodeOriginalArray(presum, N);
  }
}
 
// This code is contributed by hrithikgarg03188

<script>
        // JavaScript code for the above approach
 
        // Finds and prints the elements of
        // the original array
        function DecodeOriginalArray(presum, N)
        {
         
            // Calculating elements of original array
            for (let i = N - 1; i > 0; i--)
                presum[i] = presum[i] - presum[i - 1];
 
            // Displaying elements of original array
            for (let i = 0; i < N; i++)
                document.write(presum[i] + " ");
        }
 
        // Driver program to test above
        let presum = [45, 57, 63, 78, 89, 97];
        let N = presum.length;
 
        // Function Call
        DecodeOriginalArray(presum, N);
 
  // This code is contributed by Potta Lokesh
    </script>

45 12 6 15 11 8 

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