Home > Blockchain >  Finding minimum number of steps to reach (x,y) from (1,1) : we can increment number by using conditi
Finding minimum number of steps to reach (x,y) from (1,1) : we can increment number by using conditi

Time:09-09

a = 1
b = 1

x=int(input())
y=int(input())

def minsteps(x,y):
    if x==a and y==b:
        print(1)
        return 1
    if x<a and y<b:
        print(2)
        return 20
    
    count = 1   min(minsteps(x,x y),minsteps(x y,y))
    return count

print(minsteps(x,y))

Test case:

(3,2) (input)
2 (output)

Explanation:

1:(1,1 1) #at first step
2:(1 2,2) #at second step

CodePudding user response:

Problem statement is quite unclear and you do not really ask a clear question... Of course we understand you get an infinite loop, for the simple reason you don't have a real "breaking" statement, in most cases.

Generally speaking, I don't understand the algo goal: you start at (1,1) and you want to reach (x,y) by only adding y on x and/or x on y ? If that's it, I really don't see how it can behave properly...

Let's say you have x=10 and y=63 Then you can go to (1 63, 1) = (64,1) or to (1,63 10) = (1,73). Regardless of the case you already overpass your initial target which is (10,63). That's basically why you never enter your two if statements.

Can you please clarify ?

Note to moderators: I can't post this as a comment while it's obviously one, sorry. Will edit with a true answer once post is clarified.

CodePudding user response:

this problem seems very familiar to one that I worked on while completing the google foobar challenge.
this program is the most efficient was to find the solution of x, y...

    def solution(x, y): #finds the solution for inputs x, y
        count = 0
        while x > 1 or y >1:
            if y > x:
                y -= x
            elif x > y:
                x -= y
            else: #solution is impossible
                return 0
            count  = 1
       return count;
  • Related