Problem Name: Mathematics - Sumar and the Floating Rocks

Problem Link:

In this HackerRank in Mathematics - Sumar and the Floating Rocks solutions

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.

1 <= T <= 105
-109 <= x1, y1, x2, y2 <= 109

Sample input

0 2 4 0
2 2 5 5
1 9 8 16

Sample Output




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);
        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*/

        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;
Copy The Code & Try With Live Editor

#2 Code Example with Python Programming

Code - Python Programming


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')


Copy The Code & Try With Live Editor


[Solved] Filling Jars solution in Hackerrank - Hacerrank solution C, C++, C#, java, js, Python
[Solved] Russian Peasant Exponentiation solution in Hackerrank - Hacerrank solution C, C++, C#, java, js, Python