1

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.

2
  • 5
    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!
    – Danique
    Apr 30, 2015 at 22:34

1 Answer 1

1

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.

1
  • This is a nice solution Apr 30, 2015 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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