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
IIDIIII =(3+2)*2+4=14
IIIDII =(3+3)*2+2=14
IIIID =(3+4)*2+0=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.

  • 5
    Think: binary numbers – John Dvorak Apr 29 '15 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! – Danique Apr 30 '15 at 22:34

For example for the number of ways to go from 10 to 1000:

Let A (N) = number of ways to get from N to 1000. Calculate and store A (N) for N = 1000, 999, ..., 10.

For N = 1000, 999, ..., 501, A (N) = 1 because you cannot double the number.

For N ≤ 500, A (N) = A (2N) + A (N + 1), because you can either double and get from 2N to 1000, or increment and go from N+1 to 1000.

  • This is a nice solution – Ben Aaronson Apr 30 '15 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.