The smaller problem you need to solve is:
Given the first and last element, how many ways are there to to
fill the other elements?
In different words: How many combinations of M terms of
-1,+0,+1 are there, that add up to last-first?
A bit more formal, we want
first + d_0 + d_1 + ... + d_M-1 == last
-> d_0 + d_1 + ... + d_M-2 == last-first
This is a combinatorics problem. I'll leave it to you to find the
right formula and just pick one example:
M = 3
first = 0
last = 1
solutions:
0 +0+0+1 == 1 <- 3 different ways to sort the terms
0 +1-1+1 == 1 <- 3 different ways sort the terms
Write a function find_combinations_between(int first,int last,int
M);.
The tiny problem:
In case you have only first or last given, the solution is simply 3^M.
Back to the original problem
Once you can solve the smaller problem, getting arrays with known/unknown elements in the middle is straightforward.
Pseudocode:
int calculate( iterator begin, iterator end) {
int count = 0;
auto first = begin;
auto last = begin;
// find next known element
while ( last != end && is_empty( last ) ) {
++last;
++count;
}
// there is none
if ( last == end) return result * power_of_3( count );
// ..or recurse to the next sub-interval
return calculate(last,end) * find_combinations_between(first,last,count);
}
I think passing iterators can help for clarity a bit. The idea is to split the array into sub-intervals, such that always only first and last elements are known. power_of_3 and is_empty is only used for readability, you could probably replace it with some other call or == 0, respectively. Take the code with a grain of salt, it is meant to outline the idea but may contain mistakes.
mod 1e7
Only when the algorithm itself is working I would incorporate the
%1e7 part, hence I ignored it for this answer.
PS I am not presenting you a full solution, but rather suggest you change perspective. Your "one unknown in between two knowns" case is a very special case, but you need an overall strategy first. If you follow my recipe then all the complexity is in one place: find_combinations_between. And most importantly, in that function, you can concentrate on the combinatorics problem, while it is irrelevant whether the elements are inside some array or whatever.
PPS: As already mentioned I did not present you a full solution. And I still do not feel like giving one. The above is only how to approach the problem in a different way, but how to actually solve it was left open. As per your request I will add a bit more clarification on how to tackle the find_combinations_between.
Some visualisation may help. As the solution only depends on the difference last - first, I use first = 0 and last = D.
Lets first consider the case where D==M, ie the trivial case where we have to add +1 on every element to reach the correct result:
0
\
\
\
\
D
That was easy, right? There is only one solution. Now lets go just a tiny bit more compilcated: What if D == M-1? Then we have to add +1 for all but one element. Possible solutions are
0 0 0 0
\ \ \ |
\ \ | \
\ | \ \
| \ \ \
D D D D
ie exactly as many as there are free elements to choose. The same situation you have on the other end, when the only way to reach the right sum is to add -1 on each element (or add -1 on all but one).
It gets more complicated when +1 and -1 can be combined to get the right solution. The visualization above can still help for orientation. Think of all the paths that I didnt not draw in the above images, then you have a tree and need to find the number of possible paths from the root to a given leaf.
I don't know how to explain more without actually implementing it myself, which would mean starting to write code instead of writing the answer here ;). Hence I will again use an example and hope it helps you to find the solution.
Lets say the difference last-first is 2. Then first you need to find, for the given number of elements, lets say 4, all possible increments, that would be
+1 +1 +0 +0 = 2 // start with minimum number of +1s, ie 2 in this case
+1 +1 +1 -1 = 2 // next has 3x +1
// 4x +1 is not possible
Next you have to find all different permutations, that would be
+1 +1 +0 +0 // 4*3 because
+1 +0 +1 +0 // 4 choices for the first +1
+1 +0 +0 +1 // x3 choices for the second
+0 +1 +1 +0
+0 +1 +0 +1
+0 +0 +1 +1
+1 +1 +1 -1 // 4 different ways to place the -1
....
In total that would be 12+4=16 different ways to add +1,0 or -1 to reach from any number x to x+2 in 4 steps.
