Algorithm

Problem Name: Mathematics - Possible Path

Problem Link: https://www.hackerrank.com/challenges/possible-path/problem?isFullScreen=true

In this HackerRank in Mathematics - Possible Path solutions,

Adam is standing at point (a,b) Adam is standing at point (x,y) or not. The only operation he can do is to move to point (a + b,b) , (a,a + b),(a - b,b),(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 (or Y) 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,x and y

Constraints

  • 1 <= T <= 1000
  • 1 <= a,b,x,y <= 1018

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

Explanation

  1. (1,1) -> (2,1) -> (2,3).

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
unsigned long long int gcd(unsigned long long int,unsigned long long int);
int main()
{
    short int t;
    unsigned long long int a,b,x,y;
    scanf("%hi",&t);
    while(t--)
    {
        scanf("%llu%llu%llu%llu",&a,&b,&x,&y);
        if(gcd(a,b)==gcd(x,y))
        printf("YES\n");
        else
        printf("NO\n");
    }
    return 0;
}
unsigned long long int gcd(unsigned long long int n1,unsigned long long int n2)
{
    while(n1!=n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    return n1;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {

long long testCases;
long long gcdStart, gcdDestination;
long long startX, startY, destX, destY, quotient;
long long remainder = 12345;

cin >> testCases;

for ( long long i=0; i  <  testCases; ++i) {

    cin >> startX >> startY >> destX >> destY;

while ( remainder != 0 ) 

{

    remainder = startX % startY;

    startX = startY;

    startY = remainder;

if (remainder == 0) 
   {
        quotient = startX;
   }

}
         remainder = 12345;
         gcdStart = quotient;

while ( remainder != 0 ) 
{

    remainder = destX % destY;

    destX = destY;

    destY = remainder;


 if (remainder == 0) 
    {
        quotient = destX;
    }

}
      gcdDestination = quotient;

 if (gcdDestination == gcdStart) 
    {
        cout << "YES" << endl;
    }
 else 
    {
        cout << "NO" << endl;
    }


}



return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Python Programming

Code - Python Programming


#!/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 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()
Copy The Code & Try With Live Editor
Advertisements

Demonstration

Previous
[Solved] Most Distant solution in Hackerrank - Hacerrank solution C, C++, C#, java, js, Python
Next
[Solved] Constructing a Number solution in Hackerrank - Hacerrank solution C, C++, C#, java, js, Python