# Increment or double problem

I have a problem with an assignment. In this assignment I have to create a program which needs to calculate how many different possibilities are there to get from number a to b. To get from a to b you can only D(double) the value or I(increment) the value.

So you can have a=3 and b=14. This will get you 8 different possibilities:

``````DDII = 3*2*2+2 = 14
DID = ((3*2)+1)*2 =14
DIIIIIIII = 3*2+8 =14
IDIIIIII=(3+1)*2+6=14
IIDIIII =(3+2)*2+4=14
IIIDII =(3+3)*2+2=14
IIIID =(3+4)*2+0=14
IIIIIIIIIII=3+11=14
``````

In my current solution I'm using a breadth-first search (BFS) to calculate all the possibilities only this is very slow, because sometimes there are many possibilities and with BFS you will go through all of them. So for example if want to calculate a=10 and b=1000, this will give me 74,116,423 possibilities.

This is almost impossible to calculate with my computer and the solution I'm currently using.

What is the proper approach to take to solve this problem? Being an assignment I am not looking for the answer, I need an algorithm or other push in the right direction.

• Think: binary numbers Apr 29, 2015 at 21:14
• Hello Jan, Thank you the fast reply! I didn't had much time today, so I didn't looked at your idea. Tomorrow I'm going to think about your idea. Thanks! Apr 30, 2015 at 22:34