Algorithm
Problem Name: Mathematics -
https://www.hackerrank.com/challenges/harry-potter-and-the-floating-rocks/problem?isFullScreen=true
In this HackerRank in Mathematics -
Famous wizard Sumar moonji kumaru is stuck in a huge room and has to save Hermione Granger from a monster. Kumaru is at location P1 given by integral coordinates (x1,y1) and Hermione is at location P2 given by integral coordinates (x2,y2). Sadly P1 and P2 are the only points at which floating rocks are present. Rest of the room is without floor and underneath is hot lava.
Kumaru has to go from P1 to P2 but there are no floating rocks to walk on. Kumaru knows a spell that can make the rocks appear but only on the integral coordinates on the straight line joining P1 and P2.
How many rocks can appear at locations (x,y) on the line segment between P1 and P2 (excluding P1 and P2) which satisfy the condition that both x and y are integers?
Input Format
The first line contains a single integer T, the number of test cases. T lines follow.
Each of the following T lines contains one test case each. Each test case contains 4 integers x1, y1, x2 and y2 separated by a single space.
Output Format
A single line containing the number of rocks.
Constraints
1 <= T <= 105
-109 <= x1, y1, x2, y2 <= 109
Sample input
3
0 2 4 0
2 2 5 5
1 9 8 16
Sample Output
1
2
6
Explanation
Case 1: As shown in the figure, between (0,2) and (4,0) there's only 1 integral point (2,1) hence 1 rock.
Case 2: Between (2,2) and (5,5) lies (3,3) and (4,4), hence 2 rocks.
Case 3: Between (1,9) and (8,16) there lies 6 rocks at positions (2,10) (3,11) (4,12) (5,13) (6,14) (7,15).
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <algorithm>
using namespace std;
int gcd(int a, int b)
{
if(a == 0 || b == 0)
return (a + b);
else
return gcd(min(a, b), max(a, b)%min(a, b));
}
int main()
{
int no_of_test_cases;
scanf("%d", &no_of_test_cases);
/*Let a/b = (y2 - y1)/(x2 - x1) be the slope in the reduced form.
WE know slope = tan theta.
So, to encounter another lattice point we must move a units in the y-direction and b units in the x-direction ...
(x1 + b, y1 + a) is guaranteed to give us another lattice point because integers are being added and the slope is still the same.
Number of lattice points = (y2 - y1)/a - 1 = (x2 - x1)/b - 1 ... Subtract 1 to exclude the destination.
A further simplifaction can be made ... a = (y2 - y1)/gcd and b = (x2 - x1)/gcd.
Answer = gcd(y2 - y1, x2 - x1) - 1*/
while(no_of_test_cases--)
{
int x1, x2, y1, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
printf("%d\n", gcd( abs(x2 - x1), abs(y2 - y1) ) - 1);
}
return 0;
}
#2 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 an INTEGER.
# The function accepts following parameters:
# 1. INTEGER x1
# 2. INTEGER y1
# 3. INTEGER x2
# 4. INTEGER y2
#
def solve(x1, y1, x2, y2):
x_dist = abs(x1 - x2)
y_dist = abs(y1 - y2)
return math.gcd(x_dist, y_dist) - 1
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()
x1 = int(first_multiple_input[0])
y1 = int(first_multiple_input[1])
x2 = int(first_multiple_input[2])
y2 = int(first_multiple_input[3])
result = solve(x1, y1, x2, y2)
fptr.write(str(result) + '\n')
fptr.close()