How to solve this recursion question I saw during job interview?-CodePudding

I was asked this question during an online assessment (I'm a student looking for an SDE internship) and couldn't solve it in time (I was only given 5 minutes...). Do you guys think 5 minutes for this question is enough btw? I'm just kinda curious how good everyone else is lol.

Anyways, here's the question:
You are given two tuples of integers (A, B) and (C, D).
There are two operations you can do:
(A B, B)
(A, A B)
Write a function that returns True if (A, B) can be transformed into (C, D) using the two operations, False otherwise.

Example:

Input: A = 2, B = 3, C = 8, D = 11
Output: True

I'll put what I 'thought' I wrote during the assessment here (I'm only 70% sure). It seems to be working fine and I'm not sure why it wouldn't pass the tests. If you guys know what the problem is, or the correct solution, please lemme know! Thank you!

def func(A, B, C, D):
    if A == C and B == D:
        return True
    if A > C or B > D:  
        return False

    return func(A   B , B, C, D) or func(A, A   B, C, D)

CodePudding user response：

There's a unique path down from the target (assuming positive integers), so go that direction to avoid a large search space.

I.e. always decrease the larger coord by the smaller, or any integer multiple of the smaller that doesn't overshoot your target.

E.g. 8,11 -> 8,3 -> 2,3 is the unique path down from the target attained by decreasing the larger coord by the largest mult of the smaller that doesn't overshoot.

CodePudding user response：

You can try using BFS or DFS approach. I'd go with BFS as it'll get you there(the solution state) the fastest. Also, make sure you have a threshold to stop your loop for the cases where there is no solution (can't reach C,D)