CODEWITHSUNDEEP
algorithm
Saturn
Saturn

Reputation: 18149

Counting the minimum number of operations needed to reach a certain number

How should I implement an algorithm for this challenge?

Have three integers, A, B and C.

Your calculator starts off with the number 1, and it must reach C. To do this, you can perform two operations:

You must return the minimum number of operations needed to reach C.

Also, your calculator only has four digits, so you can expect A, B and C input to be, at most, 9999.

Example:

A = 2, B = 3, C = 10

1*A = 2 
2*A = 4 
4*A = 8 
8*A = 16 
16/B = 5 
5*A = 10

So the result would be 6 steps.

I once did it by brute-forcing the result (try lots of combinations and grab the one with the least number of steps). That was silly.

Upvotes: 2

Views: 1301

Answers (1)

amit
amit

Reputation: 178451

This can be reduced to a shortest path problem on a graph G=(V,E), where the vertices V={0,1,2,...,9999} and E = { (x,y) | y = x*a, y< 10,000 or y = x /b } U { (x,1) | x*a > 10,000 }

Now, you need to find shortest path from 1 to your target. It can be done by running a BFS, A* Search algorithm (if you find a good heuristic) or bi-directional search (which is basically BFS from the target and from the source at the same time)

EDIT:
(Note: Original answer contained a bit of a different edges set, that fits a slightly different problem. Either way - the main idea remains)

Upvotes: 6

Related Questions