You are given a non-empty list of positive integers. Your task is to figure out how many distinct numbers can be obtained by applying the following algorithm:
- Remove either the first or the last item from the list and initialize N to the corresponding value.
- Remove either the first or the last item from the list. Let's call its value v.
- Update N to either N + v or N * v.
- If the list is empty, stop here and return N. Otherwise, resume at step 2.
This is code-golf.
Detailed example
Let's say that the input is:
[ 1, 5, 2, 3 ]
We can do, for instance:
[ 1, 5, 2, 3 ] - choose 3 ==> n = 3
[ 1, 5, 2 ] - multiply by 2 ==> n = 6
[ 1, 5 ] - add 1 ==> n = 7
[ 5 ] - multiply by 5 ==> n = 35
[] - done
That's the only way of getting 35. But there are many different ways of getting, say, 11:
1 +5 +2 +3
3 +2 +1 +5
3 *2 +5 *1
etc.
All in all, we can generate 19 distinct numbers with this list. Only one example solution is given below for each of them.
10 : 3 +2 +5 *1 | 16 : 3 *1 +5 *2 | 22 : 3 +1 *5 +2 | 31 : 3 *2 *5 +1
11 : 3 *2 +5 *1 | 17 : 3 *1 *5 +2 | 24 : 1 +5 +2 *3 | 35 : 3 *2 +1 *5
12 : 3 *2 +5 +1 | 18 : 3 +1 +5 *2 | 25 : 3 +2 *5 *1 | 36 : 1 +5 *3 *2
13 : 3 +1 *2 +5 | 20 : 1 +5 *3 +2 | 26 : 3 +2 *5 +1 | 40 : 3 +1 *2 *5
15 : 1 +5 *2 +3 | 21 : 1 *5 +2 *3 | 30 : 3 *2 *5 *1 |
So, the expected answer for this input is 19.
Below are two examples of invalid solutions:
32 : 5 *3 +1 *2 -> 5 can't be chosen at the beginning
32 : 3 *5 +1 *2 -> 5 can't be chosen after 3
Test cases
[ 7 ] -> 1
[ 1, 1 ] -> 2
[ 2, 2 ] -> 1
[ 1, 2, 3 ] -> 5
[ 7, 77, 777 ] -> 8
[ 1, 5, 2, 3 ] -> 19
[ 2, 2, 11, 2, 2 ] -> 16
[ 2, 2, 2, 2, 11 ] -> 24
[ 21, 5, 19, 10, 8 ] -> 96
[ 7, 7, 7, 7, 7, 7 ] -> 32
[ 6, 5, 4, 3, 2, 1 ] -> 178
[ 1, 3, 5, 7, 5, 3, 1 ] -> 235
[ 9, 8, 6, 4, 5, 7, 3 ] -> 989
[ 7, 4, 6, 8, 5, 9, 3 ] -> 1003