Question

Can we generate actual array from prefix and suffix sum

Answer 1

Answer:

Prefix Sum:

original array : {1, 2, 3}

prefix sum array : {1, 1+2, 1+2+3}

Suffix Sum:

original array : {1, 2, 3}

suffix sum array : {3+2+1, 3+2, 3}

As per your question, the combined array seems to be sorted. Therefore

Let combined array be c[] = {1, 1+2, 3, 3+2, 1+2+3, 3+2+1} = {1, 3, 3, 5, 6, 6}

Now, finding the original sequence:

If original array has n elements then combined array will have 2*n elements

Split the array like array1 = {c[0], c[2], c[4]} and array2 = {c[1], c[3], c[5]}

array1 will now have prefix sum and array2 will have suffix sum

Now array1 is sufficient to find the original sequence (as combined array is sorted as per your question). Therefore original array would be {c[0], c[2]-c[0], c[4]-c[2]}

Answer 2

Answer:

Input : arr[] = {10, 20, 10, 5, 15}

Output : prefixSum[] = {10, 30, 40, 45, 60}

Explanation : While traversing the array, update

the element by adding it with its previous element.

prefixSum[0] = 10,

prefixSum[1] = prefixSum[0] + arr[1] = 30,

prefixSum[2] = prefixSum[1] + arr[2] = 40