# HackerRank Solution: Does Path Exist [2 Methods]

Written By - Bashir Alam

## Question: Python Possible Path [Mathematics]

Adam is standing at point (a, b) in an infinite 2D grid. He wants to know if he can reach point (x, y) or not. The only operation he can do is to move to point (a+b, b), (a, a+b), or (a, b-a) from some point (a, b) . It is given that he can move to any point on this 2D grid, i.e., the points having positive or negative(x, y) (or ) co-ordinates.

Tell Adam whether he can reach (x, y) or not.

Input format

The first line contains an integer, T, followed by T lines, each containing 4 space-separated integers i.e.a, b, xand y.

Constraints

• 1<=T<=1000
• 1<=a, b, x, y <= 10^18

Output format

For each test case, display YES or NO that indicates if Adam can reach (x, y) or not.

Sample Input:

```3
1 1 2 3
2 1 2 3
3 3 1 1```

Sample Output:

```YES
YES
NO```

## Possible Solutions

Now we will discuss the possible solutions to the given problem. The following code is already been given in the by the Hacker Rank:

``````#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'solve' function below.
#
# The function is expected to return a STRING.
# The function accepts following parameters:
#  1. LONG_INTEGER a
#  2. LONG_INTEGER b
#  3. LONG_INTEGER x
#  4. LONG_INTEGER y
#

def solve(a, b, x, y):

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

t = int(input().strip())

for t_itr in range(t):
first_multiple_input = input().rstrip().split()

a = int(first_multiple_input)

b = int(first_multiple_input)

x = int(first_multiple_input)

y = int(first_multiple_input)

result = solve(a, b, x, y)

fptr.write(result + '\n')

fptr.close()
``````

As you can see, we only have to complete the `solve()` function. The rest all is given there.

### Solution-1: Using `math.gcd()` method

Let us use the `math.gcd` method to solve the given problem:

``````import math
import os
import random
import re
import sys

def solve(a, b, x, y):
if math.gcd(a, b) == math.gcd(x, y):
return "YES"
return "NO"

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

t = int(input().strip())

for t_itr in range(t):
first_multiple_input = input().rstrip().split()

a = int(first_multiple_input)

b = int(first_multiple_input)

x = int(first_multiple_input)

y = int(first_multiple_input)

result = solve(a, b, x, y)

fptr.write(result + '\n')

fptr.close()
``````

Everything was already given except the solve function. The `solve()` function uses the `math.gcd()` function (which stands for "greatest common divisor") to find the greatest common divisor of the first pair of parameters (a and b) and then compare it to the greatest common divisor of the second pair of parameters (x and y). If the two greatest common divisors are equal, the function returns the string "`YES`", otherwise it returns "`NO`".

The function is checking if the two pairs of numbers have the same greatest common divisor. If they do, it returns '`YES`', if not it returns '`NO`'.

### Solution-2: Multi conditions in one line

In Python, we can use the if and else statements in one line as well. In this solution, we will use the if and else statements in the online line:

``````import math
import os
import random
import re
import sys

def solve(a: int, b: int, x: int, y: int):
return 'YES' if math.gcd(a, b) == math.gcd(x, y) else 'NO'

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

t = int(input().strip())

for t_itr in range(t):
first_multiple_input = input().rstrip().split()

a = int(first_multiple_input)

b = int(first_multiple_input)

x = int(first_multiple_input)

y = int(first_multiple_input)

result = solve(a, b, x, y)

fptr.write(result + '\n')

fptr.close()``````

Notice that the `solve()` method has the solution in only one line. The function first performs the same computation as before: It calculates the greatest common divisor of the two pairs of numbers (a, b) and (x, y) using the `math.gcd()` function. It then compares the two results and returns '`YES`' if they are equal and '`NO`' if they are not.

The main difference is that this version uses a more concise and readable syntax to achieve the same functionality, by using the ternary operator the code becomes more readable.

## Summary

In this short article, we discussed how we can solve the Possible path problem from Hacker rank. We discussed two possible methods to solve the problem and explained each method deeply.

Question on Hacker Rank: Possible Path

Didn't find what you were looking for? Perform a quick search across GoLinuxCloud

If my articles on GoLinuxCloud has helped you, kindly consider buying me a coffee as a token of appreciation. For any other feedbacks or questions you can either use the comments section or contact me form.