Prefix sum problems: Get original array from Prefix sum array

Problem Statement:

You are given a prefix sum array. You need to find the original array.

Example:

Input: [1, 3, 6, 10]

Output: [1, 2, 3, 4]

Solution Explanation:

Solution is very simple.

Below are the 2 conditions:

arr[0] = prefixSum[0]

for index i > 0

arr[i] = prefixSum[i] – prefixSum[i-1]

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;


vector<int> solution(vector<int>& nums) 
{
    int n = nums.size();
    vector<int> arr(n);

    arr[0] = nums[0];
    for (int i = 1; i < n; i++) {
        arr[i] = nums[i] - nums[i - 1];
    }

    return arr;
}


int main()
{
    vector<int> arr =  {1, 3, 6, 10};
  
    vector<int> result = solution(arr);

	for (int num : result) 
	{
        cout << num << " ";
    }
    
    return 0;
}

Output

1 2 3 4