Let us consider sequence of n numbers as follows:
x1 x2 x3 . . . xn
The prefix sums are:
x1 (x1+x2) (x1+x2+x3) (x1+x2+x3+x4) . . . (x1+x2+x3+…xn)
= n.x1 + (n-1).x2 + (n-2).x3 + . . . xn
Similarly, the suffix sums are:
xn (xn+x(n-1)) (xn+x(n-1)+x(n-2)) (xn+x(n-1)+x(n-2)+x(n-3)) . . . (xn+x(n-1)+x(n-2)+x(n-3)…x1)
= n.xn + (n-1).x(n-1) + (n-2).x(n-2) + . . . x1
If we add all prefix and suffix sums, the combined term becomes:
n.x1 + (n-1).x2 + (n-2).x3 + . . . xn
+
x1 + 2.x2 + 3.x3 + . . . n.xn
= (n+1)x1 + (n+1)x2 + (n+1)x3 + . . . (n+1)xn
= (n+1)(x1+x2+x3+…+xn)
= (n+1) . sum(x)
The value for sum(x) can be determined as follows:
sum(x) = (sum of all prefix and suffix sums) / (n+1)
Note that sum(x) may not be always the largest value especially if any of numbers in original list (x1 to xn) contains negative values. We can use above formula to determine the value of sum(x) in all cases, whether original sequence contains +ve or -ve numbers, it doesn’t matter, the formula will give us the correct sum(x) value.
For example, consider following example with suffix and prefix sums (in some random order):
5 3 10 7 5 10
Sum of all above numbers is: 40 and n=3 so the sum of original numbers is 40/(3+1) = 10
I generated above prefix and suffix sums using 5 -2 7. There are other possible sequences that can result in same prefix and suffix sums, but their sum has to be 10.
Note that 10 appears twice. If sum(x) does not appear twice in given prefix and suffix sums, then, it is an invalid input and no solution is possible. So the result in such case is zero.
Remove the two sum(x) numbers from the list, and arrange the remaining numbers in ascending order:
3 5 5 7
This forms a list of numbers whose count is 2(n-1) which is 2.(3-1) = 4 in this case.
Notice that addition of first and last numbers is also sum(x). Similarly, the addition of second and last but one is also sum(x). This is the case for all such pairs. If it is not, then, solution is not possible and the result is zero.
Why is this so? How can we draw such a conclusion?
Consider the original sequence: 5 -2 7
following table shows prefix and suffix sums for each of the position as follows:
Original numbers : 5 -2 7
Prefix sums(up to the position) : 5 3 10
Suffix sums(up to next position) : 5 7 0
Addition of prefix & suffix sum : 10 10 10
In above table, in each column, the value for prefix and suffix sums mentioned are for the two sub-lists of the origianl sequence. The addition of these two sub-lists equals the addition of all numbers from the entire list.
For example:
at position 1, the two sub-lists are: (5) (-2 7)
at position 2, the two sub-lists are: (5, -2) (7)
and at position 3, the two sub-lists are: () (5 -2 7)
The first sub-list is the prefix sum at that particular position, second sub-list is the suffix sum. Their sum must equal sum(x). Basically, it does not matter at which position the list of numbers is split in two parts; the sum of two sub-lists always must equal to the sum of entire list. Hence the proof.
Hence for each prefix sum there must exist one suffix sum such that their addition is equal to sum(x). If this is not the case, then, solution is not possible. And the answer is zero in such case.
So in above example, there are 2 pairs of prefix and suffix sums: (3 7) and (5 5).
One particular sequence of prefix sums uniquely defines sequence of original numbers. So to compute the number of original sequences, we need to determine the number of possible sequences of prefix sums.
For the given example, following are all possible permutations:
Case 1 Case 2 Case 3 Case 4
Prefix sums : 3 5 10 7 5 10 5 3 10 5 7 10
Suffix sum up to next position: 7 5 0 3 5 0 5 7 0 5 3 0
original numbers : 3 2 5 7 -2 5 5 -2 7 5 2 3
For this example, the answer i.e. the count for different possible sequences is 4.
The prefix sums can be generated by permuting in following manner:
-
From the pair of prefix and suffix sum that adds to sum(x), any number can be prefix sum. So if these are different numbers, then, the possibilities are doubled.
-
We can arrange (n-1) prefix sums in any order. If all the prefix sum values are different, then, we will have (n-1)! number of counts for prefix sums. But if some prefix sums are repeated, then, the count can be obtained by using npr formula.
In general, there exists (n-1) pairs of prefix and suffix sums that add exactly to sum(x). Out of these, if any pair repeats, then we maintain a count of how many times that pair repeats. Let us say we have got “k” different pairs of prefix and suffix sums with counts as n1, n2, n3, . . . , nk where k is the number of unique pairs. And let us say “u” as the number of pairs containing different values for prefix and suffix sum, then the formula for count is:
(n-1)! * 2 ^ u
(n1! * n2! * n3! . . . nk!)
For above example:
n = 3
k = 2
n1 = 1 (pair: (3 7) appears once)
n2 = 1 (pair: (5 5) appears once)
u = 1 because there is only one pair (3 7) that has prefix sum != suffix sum.
Hence the count becomes:
(3-1)! * 2 ^ 1
________________ = 2*2 / 1 = 4
(1! * 1!)