Join Us
Loading Similar Posts
Entering edit mode
Problem 1: Is Possible
Solution: Reverse Traversal using Subtraction The most efficient way to solve this problem is to work backward from the target pair (c, d) to the source pair (a, b). The forward operations, (x, y) -> (x+y, y) and (x, y) -> (x, x+y), cause the numbers to grow, leading to an exponentially large search space. However, the inverse operations are deterministic. A pair (x, y) could only have been formed from (x-y, y) if x > y, or from (x, y-x) if y > x. This reverse process is mathematically equivalent to the subtractive version of the Euclidean algorithm and guarantees finding the unique path if one exists.
The logic is as follows:
Start from Target: Initialize the current pair with the target values
(c, d).Iterative Reduction: Loop as long as the current pair's values are greater than or equal to the source pair's values (
c >= aandd >= b).Check for Match: Inside the loop, if the current pair
(c, d)equals the source(a, b), a valid path has been found, and the answer is 'Yes'.Apply Inverse Operation:
If
c > d, the only possible predecessor was(c-d, d). Updatectoc-d.If
d > c, the only possible predecessor was(c, d-c). Updatedtod-c.
Handle Dead End: If
c == dbut the pair is not the source(a, b), no further reduction is possible with positive integers. This path is a dead end, so the loop is terminated.Final Decision: If the loop finishes without finding a match (either by overshooting the source values or hitting a dead end), it is impossible to reach the target from the source. The answer is 'No'.
#include <iostream>
#include <string>
#include <vector>
std::string isPossible(int a, int b, int c, int d) {
while (c >= a && d >= b) {
if (c == a && d == b) {
return "Yes";
}
if (c > d) {
c = c - d;
} else if (d > c) {
d = d - c;
} else {
break;
}
}
return "No";
}
Complexity Analysis:
Time Complexity:
O(c + d). The algorithm's runtime is determined by the number of subtractions needed to reduce(c, d). In the worst case (e.g., reducing(1000, 1)), this is a linear number of steps. While related to the Euclidean algorithm, the subtractive version can be slower than the modulo-based version, but it is highly efficient for the given constraints.Space Complexity:
O(1). The algorithm uses a fixed number of variables to store the current pair's values. The memory usage does not scale with the size of the input numbers.
Entering edit mode
Problem 2: Do They Belong?
Solution: Cross Product Method for Collinearity and Containment This geometric problem is solved robustly by breaking it into two parts: a triangle validity test and a point containment test. Both parts are handled using the 2D cross product, which is equivalent to calculating the signed area of a triangle. This integer-based method avoids the precision errors and edge cases (like division by zero) associated with floating-point arithmetic, making it ideal for this problem's constraints.
The logic is as follows:
Collinearity Test: First, determine if the vertices
a,b, andcform a valid, non-degenerate triangle. This is done by checking if they are collinear. Three points are collinear if and only if the signed area of the triangle they form is zero. If the area is zero, the triangle is degenerate, and the function returns0.Point Containment Test: If the triangle is valid, we test if points
pandqare inside. A pointPis inside or on the boundary of a triangleABCif and only if it lies on the same side of all three lines defined by the triangle's edges (AB,BC,CA).Same-Side Check: The "side" of a point relative to a directed edge is determined by the sign of the cross product. For a counter-clockwise triangle
ABC, pointPis inside if the signed areas of trianglesABP,BCP, andCAPare all non-negative. The logic works consistently regardless of the triangle's initial orientation (clockwise or counter-clockwise).Categorize Scenario: Based on whether
pandqare inside the triangle, the function returns the corresponding integer code from 1 to 4.
#include <iostream>
long long signed_area(long long p1x, long long p1y, long long p2x, long long p2y, long long p3x, long long p3y) {
return (p2x - p1x) * (p3y - p1y) - (p3x - p1x) * (p2y - p1y);
}
bool is_inside(long long px, long long py, long long x1, long long y1, long long x2, long long y2, long long x3, long long y3, long long main_area) {
long long area1 = signed_area(x1, y1, x2, y2, px, py);
long long area2 = signed_area(x2, y2, x3, y3, px, py);
long long area3 = signed_area(x3, y3, x1, y1, px, py);
if (main_area > 0) {
return area1 >= 0 && area2 >= 0 && area3 >= 0;
} else {
return area1 <= 0 && area2 <= 0 && area3 <= 0;
}
}
int pointsBelong(int x1, int y1, int x2, int y2, int x3, int y3, int xp, int yp, int xq, int yq) {
long long area_abc = signed_area(x1, y1, x2, y2, x3, y3);
if (area_abc == 0) {
return 0;
}
bool p_inside = is_inside(xp, yp, x1, y1, x2, y2, x3, y3, area_abc);
bool q_inside = is_inside(xq, yq, x1, y1, x2, y2, x3, y3, area_abc);
if (p_inside && !q_inside) {
return 1;
} else if (!p_inside && q_inside) {
return 2;
} else if (p_inside && q_inside) {
return 3;
} else {
return 4;
}
}
Complexity Analysis:
Time Complexity:
O(1). The algorithm performs a fixed number of arithmetic operations (multiplications, subtractions, and comparisons) to determine the result. The number of calculations does not depend on the magnitude of the coordinates.Space Complexity:
O(1). The solution uses only a few variables to store coordinates and intermediate area calculations. No additional memory that scales with input size is required.
