Find minimum number of iterations to reach a certain sum

Question

I'm trying to solve this problem since weeks, but couldn't arrive to a solution. You start with two numbers X and Y both equal to 1. Only valid options are X+Y or Y+X at a time. We need to find minimum number of iterations need to reach a specific number.

eg : if the number is 5

X=1, Y=1; X = X+Y

X=2, Y=1; Y = X+Y

X=2, Y=3; Y = Y+X

X=2, Y=5; Stop answer reached 

My take : If a number is odd let's say 23, decrement by 1. Now value = 22. Find the largest number that divides 22 = 11. Now reach the number by adding 1's so that:

X=11; Y=1 ; Y=Y+X

X=11; Y=12; X=X+Y

X=23, answer reached

But the problem with this approach is I cannot recursively reach a specific number, as even if I reach a certain point, say X = required value, the Y value gets misplaced and I cant reuse it to reach another value

Answer 1

Now I can give an O(nlogn) solution.

The method seems like greatest common divisor

Use f(x, y) express the minimum number of iterations to this state. This state can be reached by f(x-y, y) if x>y or f(x,y-x) if x<y. We can see that the way to reach state (x, y) is unique, we can calculate it in O(logn) like gcd.

The answer is min( f(n, i) | 1 <= i < n) so complexity is O(nlogn)

python code:

def gcd (n, m):
    if m == 0:
        return n
    return gcd (m, n%m)

def calculate (x, y):
    if y == 0:
        return -1
    return calculate (y, x%y) + x/y

def solve (n):
    x = 0
    min = n
    for i in xrange (1, n):
        if gcd (n, i) == 1:
            ans = calculate (n, i)
            if ans < min:
                min = ans
                x = i
    print min

if __name__ == '__main__':
    solve (5)

Answer 2

If the numbers are not that big (say, below 1000), you can use a breadth-first search.

Consider a directed graph where each vertex is a pair of numbers (X,Y), and from each such vertex there are two edges to vertices (X+Y,Y) and (X,X+Y). Run a BFS on that graph from (0,0) until you reach any of the positions you need.