This is a problem related to prefix and suffix sums. Before mentioning the actual problem, let me first explain what are prefix and suffix sums.
What is mean by prefix sum?
Consider an example for sequence of 3 integer numbers: 5 -2 7
The prefix numbers are: 5 3 10
These are generated as follows:
5 (5+ (-2)) (5 + (-2) + 7)
= 5 3 10
What are suffix sums?
For the same above example of 3 integer numbers, the suffix sums are: 7 5 10
These are generated as follows:
7 (7 + (-2)) (7 + (-2) + 5)
= 7 5 10
Problem:
Determine the number of different possible sequences of integers that can generate given prefix and suffix sums.
For example, following are all the prefix and suffix sums in some random order:
3 5 7 10 5 10
Since the count of above numbers is 6, the original sequence of numbers has to be 3. So the task is to find out how many different sequences of 3 integer numbers can result in same values of above mentioned prefix and suffix sums?
For this particular example, following are all possible sequences of 3 integer numbers whose prefix and suffix sums are: 3 5 7 10 5 10
5 -2 7
7 -2 5
3 2 5
5 2 3
The count of all possible integer sequences is 4 and hence the answer is 4 for this particular example.
In general, the problem can be stated as: Find out the count of sequences of n integer numbers whose prefix and suffix sums are equal to the given 2*n integer numbers mentioned in random order.
Algorithm
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
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 original 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:
1. 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.
2. 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!)
What is mean by prefix sum?
Consider an example for sequence of 3 integer numbers: 5 -2 7
The prefix numbers are: 5 3 10
These are generated as follows:
5 (5+ (-2)) (5 + (-2) + 7)
= 5 3 10
What are suffix sums?
For the same above example of 3 integer numbers, the suffix sums are: 7 5 10
These are generated as follows:
7 (7 + (-2)) (7 + (-2) + 5)
= 7 5 10
Problem:
Determine the number of different possible sequences of integers that can generate given prefix and suffix sums.
For example, following are all the prefix and suffix sums in some random order:
3 5 7 10 5 10
Since the count of above numbers is 6, the original sequence of numbers has to be 3. So the task is to find out how many different sequences of 3 integer numbers can result in same values of above mentioned prefix and suffix sums?
For this particular example, following are all possible sequences of 3 integer numbers whose prefix and suffix sums are: 3 5 7 10 5 10
5 -2 7
7 -2 5
3 2 5
5 2 3
The count of all possible integer sequences is 4 and hence the answer is 4 for this particular example.
In general, the problem can be stated as: Find out the count of sequences of n integer numbers whose prefix and suffix sums are equal to the given 2*n integer numbers mentioned in random order.
Algorithm
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
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 original 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:
1. 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.
2. 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!)
