HackerRank Fundamentals – Sumar and the Floating Rocks

Challenge: Sumar and the Floating Rocks

Subdomeniu: Fundamentals (fundamentals)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464734364

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/harry-potter-and-the-floating-rocks/problem

Cerinta

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 (x<sub>1</sub>,y<sub>1</sub>) and Hermione is at location P2 given by integral coordinates (x<sub>2</sub>,y<sub>2</sub>). 
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 x<sub>1</sub>, y<sub>1</sub>, x<sub>2</sub> and y<sub>2</sub> separated by a single space. 

**Output Format**  
A single line containing the number of rocks.

**Constraints**  
1 <= T <= 10<sup>5</sup>  
-10<sup>9</sup> <= x<sub>1</sub>, y<sub>1</sub>, x<sub>2</sub>, y<sub>2</sub> <= 10<sup>9</sup>

**Sample input**  

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

**Sample Output**

    1
    2
    6
    
**Explanation**   

![2Dplane](https://hr-challenge-images.s3.amazonaws.com/1318/integralcoordinates.png)

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

Cod sursa

// https://www.hackerrank.com/challenges/harry-potter-and-the-floating-rocks

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

int main() {
    int t, x1, y1, x2, y2, g;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        g = gcd(y2 - y1, x2 - x1);
        printf("%d\n", g > 0 ? g - 1 : -g - 1);
    }
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    return 0;
}