Phil15 Phil15 - 5 days ago 7
C++ Question

Given an integer n, return the number of ways it can be represented as a sum of 1s and 2s

For example:

5 = 1+1+1+1+1

5 = 1+1+1+2

5 = 1+1+2+1

5 = 1+2+1+1

5 = 2+1+1+1


5 = 1+2+2

5 = 2+2+1

5 = 2+1+2


Can anyone give a hint for a pseudo code on how this can be done please.
Honestly have no clue how to even start.
Also this looks like an exponential problem can it be done in linear time?

Thank you.

Answer

In the example you have provided order of addends is important. (See the last two lines in your example). With this in mind, the answer seems to be related to Fibonacci numbers. Let's F(n) be the ways n can be written as 1s and 2s. Then the last addened is either 1 or 2. So F(n) = F(n-1) + F(n-2). These are the initial values:

F(1) = 1 (1 = 1)
F(2) = 2 (2 = 1 + 1, 2 = 2)
Comments