HackerRank Solution: Does Path Exist [2 Methods]

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):
    # write your code here

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[0])

        b = int(first_multiple_input[1])

        x = int(first_multiple_input[2])

        y = int(first_multiple_input[3])

        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[0])

        b = int(first_multiple_input[1])

        x = int(first_multiple_input[2])

        y = int(first_multiple_input[3])

        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[0])

        b = int(first_multiple_input[1])

        x = int(first_multiple_input[2])

        y = int(first_multiple_input[3])

        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.

 

Further Readings

Question on Hacker Rank: Possible Path