Reaching points- Leetcode

#1

I was going through different approach than recursion and found a code in discussion page. Can u help me understand a part of code in this
ques-> https://leetcode.com/problems/reaching-points/

code->https://ide.codingblocks.com/s/225476

i want to know what’s the use of the multiplication term in this?

#2

Hey @mikkyimran
Intuition
Every parent point (x, y) has two children, (x, x+y) and (x+y, y) . However, every point (x, y) only has one parent candidate (x-y, y) if x >= y , else (x, y-x) . This is because we never have points with negative coordinates.

Diagram of successive parents of the target point
Diagram of successive parents of the target point2256×960 138 KB

Looking at previous successive parents of the target point, we can find whether the starting point was an ancestor. For example, if the target point is (19, 12) , the successive parents must have been (7, 12) , (7, 5) , and (2, 5) ; so (2, 5) is a starting point of (19, 12) .

Algorithm

Repeatedly subtract the smaller of {tx, ty} from the larger of {tx, ty} . The answer is true if and only if we eventually reach sx, sy .

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

@Aarnav-Jindal-1059677350830863 Based on your advice, implemented this but it doesn’t work for certain cases.

public boolean helper(int x, int y, int tx, int ty){
    while(tx > x && ty > y){
        if(tx > ty) tx -= ty;
        else ty -= tx;
    }
    if(tx == x && ty == y) return true;
    return false;
}

Fails for:-
3
3
12
9