PROBLEM LINK:
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!