Is it possible to find the original sequence of integers from its prefix sums and suffix sums?

842 views Asked by At

Is there a way to find the initial sequence from its prefix sums and suffix sums?

Prefix sum at ith position is the sum of all elements from beginning to ith position.

Suffix sum at ith position is the sum of all elements from last to ith position in reverse order.

For an example, the combined (prefix sums and suffix sums) sequence is as follows:

{1, 3, 3, 5, 6, 6}

The initial sequence was: {1, 2, 3}

Prefix sums: {1, 3, 6}, Suffix sums: {6, 5, 3}

In combined: {1, 3, 3, 5, 6, 6}

May be in some cases there are multiple possibilities.

1

There are 1 answers

3
suhas_partha On

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:

  1. If original array has n elements then combined array will have 2*n elements
  2. Split the array like array1 = {c[0], c[2], c[4]} and array2 = {c[1], c[3], c[5]}
  3. array1 will now have prefix sum and array2 will have suffix sum
  4. 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]}

int length = combined_array.length/2;
int []prefix_breakup = new int[length];
int []original = new int[length];

for(int i=0; i<length ; i++){
    if( i%2 == 0 ){
        prefix_breakup[i] = combined_array[i];
    } 
}

original[0] = prefix_breakup[0];

for(int i=1; i<length ; i++){
    original[i] = prefix_breakup[i] - prefix_breakup[i-1];
}