RACHCHAL - Editorial

PROBLEM LINK:

Practice

Author: Sakchi Agarwal
Tester: Sparsh Kedia
Editorialist: Ayush Shukla

DIFFICULTY:

SIMPLE

PREREQUISITES:

GCD

PROBLEM:

You have to go from (X_1,Y_1) to (X_2,Y_2) and you have to take K steps always. Find the minimum value of K for which the you have to take minimum number of steps to reach the final point from starting point.

EXPLANATION:

Let horizontal length to be covered be h where (h = abs(X_1-X_2)) and vertical distance to be covered be v where (v = abs(Y_1-Y_2)). Now it is sure that in one step we can travel only vertical or horizontal steps. So it is sure that K should be a common divisor of h and v and to keep number of steps minimum K should be maximum possible divisors of h and v.Therefore required K will be G.C.D of h and v.

SOLUTIONS:

Setter's Solution
    #include <bits/stdc++.h>
using namespace std;
#define ll long long
 
main(){
    ll q,x1,x2,y1,y2;
	cin >> q; //NUMBER OF QUERIES
			while(q--)
			{
				cin>>x1>>y1>>x2>>y2;
				ll h=abs(x1-x2);
				ll v=abs(y1-y2);
				ll ans = __gcd(h,v);
				cout<<ans<<"\n";
			}
} 
Tester's Solution
import math
t = int(input())
while t>0 : 
	x1,y1,x2,y2 = [int(x) for x in input().split()]
	ans = math.gcd(x2-x1, y2-y1)
	print (ans)
	t = t-1  

Feel free to share your approach.
Happy Coding!