Unique values of expressions using given number of 2's

Question

Given number of 2's how many unique values can be formed by building an expressions out of at most the given number of 2's involving addition or multiplication.

For example, if n = 2, we can form 2 different values:

2 + 2 = 4
2 * 2 = 4
2     = 2

For n = 3, we can form 4 different values (2, 4, 6 and 8):

2 * 2 * 2 = 8
2 * 2 + 2 = 6
2 + 2 * 2 = 6
2 + 2 + 2 = 6
2 * 2     = 4
2 + 2     = 4
2         = 2

I want to know for any n, the number of different possible values.

I tried all possible combinations and adding them to hash map, but as n increases the comibnations increase exponentially so brute force won't work. I need another way of calculating or a generalized mathematical formula.

Can it be solved using Dynamic Programming, because I see many sub problems which are used repeatedly.

Answer 1

The other answers so far assume that we want to count the number of distinct expressions. This answer assumes that we are looking for the number of different values these expressions can evaluate to.

Let's say you have an expression of size at most n. Then we can rewrite it as 2^e[1] + 2^e[2] + ... + 2^e[m] with e[i] >= 1 and e[1] + e[2] + ... + e[m] <= n.

Let's assume e[1] <= e[2] <= ... <= e[m]. If e[i] = e[i+1] for some i, then we can replace the two equal exponents by the single exponent e[i] + 1, since 2^e[i] + 2^e[i+1] = 2 * 2^e[i] = 2^{e[i] + 1}. Since e[i] + 1 <= e[i] + e[i+1], the new sequence results in the same value, and still fulfills the condition that the sum of all exponents is smaller than or equal to n.

So we only need to count the number of different sequences of exponents 0 < e[1] < e[2] < ... < e[m]. It is clear that every one of those represents a different value, because the binary representation of a number is unique (and the distinct exponents represent exactly a binary representation).

We can use dynamic programming to count these sequences, for example by picking the exponents from highest to lowest.

Let's define f(n,hi) as the number of different ways to choose distinct exponents that sum up to no more than n and where the highest exponent is <= hi. At every step, we can either choose the next highest exponent arbitrarily between 1 and min(hi, n) or stop choosing exponents. So we have the recurrence

f(0, hi) = 1  for all hi >= 0
f(n, hi) = 1 + sum(e = 1 to min(hi, n), f(n - e, e - 1))

Which leads to a simple dynamic program to solve the problem. The answer is f(n,n) - 1. We need to subtract one, because we also counted the possiblity to not choose any exponents, which results in the sum 0. This is however not allowed by the problem statement.

Here are a few results:

f(1,1) - 1 = 1
f(2,2) - 1 = 2
f(3,3) - 1 = 4
f(4,4) - 1 = 6
f(5,5) - 1 = 9
f(6,6) - 1 = 13
f(7,7) - 1 = 18
f(8,8) - 1 = 24
f(9,9) - 1 = 32
f(10,10) - 1 = 42
f(11,11) - 1 = 54
f(12,12) - 1 = 69
f(13,13) - 1 = 87
f(14,14) - 1 = 109

Answer 2

If there are no parentheses involved, then:

Not a programming question, but a combinatorics one. The operands are fixed, and you are just selecting N-1 operators to place between them from a pool of 2 (+, *). There are 2^(N-1) ways of selecting operands.

N=2: 2^(2-1) = 2^1 = 2 (+, *)
N=3: 2^(3-1) = 2^2 = 4 (++, +*, *+, **)

No programming required, just maths.

EDIT: As Niklas B. points out, your own examples do not match the criteria you set out. The formula above is for "exactly N twos". If you're looking for "at most N twos", interpreted as "between 1 and N twos" (because I'm not sure what the result would be if you have 0 of them), then it's 2^N-1:

N=2: 2^2-1 = 4-1 = 3 (+, *, none)
N=3: 2^3-1 = 8-2 = 7 (++, +*, *+, **, +, *, none)

FURTHER EDIT: If you're counting values, then you do need some programming. The easiest solution is to use a hash map with keys that are the values, and count frequencies as you brute-force through the combinations. Dynamic Programming in this case would be more trouble than it's worth, seeing as the complexity is O(N^2), and you probably aren't trying to calculate million-operand formulae, while the bit with operator precedence would make for a not very intuitive algorithm.