Reaching Points

10 Prerequisite LeetCode Problems

“Reaching Points” requires the understanding of modular arithmetic and backtracking to solve. The problem is to check whether it’s possible to start from point (sx, sy) and eventually arrive at (tx, ty) by repeatedly moving along the vectors (sx, sy + sx) or (sx + sy, sy).

Here are 10 problems for practice:

  1. 365. Water and Jug Problem: A similar problem that involves figuring out a way to measure an exact amount of water given two jugs with capacities x and y liters.

  2. 991. Broken Calculator: In this problem, you are required to find the minimum number of operations needed to display the number Y on a broken calculator that can only double its display number or decrement its display number.

  3. 754. Reach a Number: A problem where you’re tasked to reach a target number by moving along the number line and figuring out the smallest number of steps it would take.

  4. 279. Perfect Squares: A problem that requires finding the least number of perfect square numbers that sum to a given number.

  5. 279. Perfect Squares: An interesting problem that involves finding the minimum total number of squares that sum to n.

  6. 372. Super Pow: A problem that involves finding the result of a super large power operation with modulo operation.

  7. 781. Rabbits in Forest: In this problem, you need to apply mathematical reasoning to figure out the minimum number of rabbits that could be in the forest.

  8. 396. Rotate Function: This problem requires understanding of how rotating an array affects the sum of the array’s elements.

  9. 621. Task Scheduler: It’s about finding a schedule that will allow a CPU to finish all its tasks as quickly as possible given certain constraints.

  10. 134. Gas Station: A problem that involves traversing through a circular route and figuring out the starting gas station that will allow us to complete the journey.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        while sx < tx and sy < ty:
            if tx < ty:
                ty %= tx
            else:
                tx %= ty
                
        if sx == tx and sy <= ty and (ty - sy) % sx == 0:
            return True
        elif sy == ty and sx <= tx and (tx - sx) % sy == 0:
            return True
        
        return False

This method continuously reduces the target point (tx, ty) until it’s no longer larger than the starting point (sx, sy) in both coordinates. This is done by subtracting the smaller value from the larger one, effectively moving the target point closer to the start. The reduction process repeats until the target point is either reached or it’s confirmed that it cannot be reached.

The first conditional checks if the target and starting x-coordinates match and whether the y-coordinate of the target is at or beyond the starting y-coordinate. If these conditions are satisfied and the difference in y-coordinates is a multiple of sx, it means that we have reached the target point through a series of valid moves, and we return True.

The second conditional checks the analogous case but with the roles of x and y swapped.

If neither of these conditions are satisfied, we return False to indicate that the target point cannot be reached from the start.

Problem Classification

This problem falls under the category of mathematical puzzles or problems, with a touch of geometrical elements (considering the points in 2D space) and recursive logic.

What Components:

  1. sx, sy: The starting coordinates.
  2. tx, ty: The target coordinates.
  3. Operation: The transformation operation that can be applied to a point (x, y) to convert it to either (x, x + y) or (x + y, y).
  4. Goal: Determine if it’s possible to transform the starting point to the target point using the allowed operation.

This problem is a form of “reachability” problem where we are given a starting state (sx, sy), an ending state (tx, ty), and allowed transformations, and we need to determine if the end state can be reached from the start state using only these transformations. The problem is recursive in nature as the transformation operation could potentially be applied repeatedly.

It could also be considered as a problem in the “pathfinding” or “graph traversal” domains, where each point represents a node and each transformation operation represents an edge connecting two nodes, and we are looking for a path from the start node to the end node.

Such problems can often be solved using depth-first search (DFS), breadth-first search (BFS), or some sort of greedy algorithm, depending on the exact constraints and properties of the problem. Here, a kind of greedy algorithm can be used, always choosing the operation that brings the current point closest to the target point.

Thought Process

This problem may initially seem like it should be solved by starting from the initial point (sx, sy) and performing operations until we reach (tx, ty) or determine that it’s impossible. However, this approach is problematic for a couple of reasons. First, it’s not clear which of the two operations we should choose at each step. Second, since the numbers can get very large (up to 10^9), we could end up performing a huge number of operations.

A key insight to solve this problem is to consider working backwards: start from the target point (tx, ty) and try to go back to the starting point (sx, sy). The reason this works is because there’s exactly one way to go backwards. When you are at a certain point (x, y) where x ≠ y, there’s only one previous step you could have taken to get there because one coordinate is larger than the other.

So, the general approach can be summarized as:

  1. Start from the target point (tx, ty).
  2. While the target point is not equal to the starting point, perform the reverse of the operation that could have been used to reach the current point from the previous point.
  3. If we reach the starting point (sx, sy), return True. If we end up with a point that is out of the bounds of the starting point, return False.

In terms of specific steps in the Python code:

  1. We’ll initiate a while loop that continues until tx,ty is not equal to sx,sy.
  2. Inside the loop, we’ll check if tx > ty. If true, we’ll subtract ty from tx. If not, we’ll subtract tx from ty.
  3. If we reach a point where tx=sx and ty=sy, we return True.
  4. If tx < sx or ty < sy (i.e., we’ve passed the starting point), we return False.

Python Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        while tx >= sx and ty >= sy:
            if tx == sx and ty == sy:
                return True
            elif tx > ty:
                tx -= ty
            else:
                ty -= tx
        return False

This code will correctly solve the problem within the constraints, as it efficiently reduces the problem size at each step. The while loop runs until the target point (tx, ty) becomes less than the starting point (sx, sy) or until it matches the starting point. Each operation in the while loop runs in constant time, so the time complexity is proportional to the number of iterations of the while loop, which is typically much less than the magnitude of the input values.

Language Agnostic Coding Drills

For the reachingPoints method:

  1. Dissect the code and identify each distinct concept it contains:
  • Looping: The while loop is used to reduce tx and ty until they are not both greater than sx and sy.
  • Conditionals: if-else conditions are used to determine which of tx or ty should be reduced.
  • Modulo operation: The modulo operation is used to reduce tx or ty.
  • Boolean operators: The operators ‘and’ and ‘==’ are used to compare values and return a Boolean result.
  1. Once you’ve identified these coding concepts or drills, list them out in order of increasing difficulty.
  • Looping: Basic concept used in almost every program, easy to understand.
  • Conditionals: A bit more complex than looping, but still a fundamental concept.
  • Boolean operators: These require a solid understanding of logic, but are still relatively straightforward.
  • Modulo operation: This can be tricky for beginners to grasp, especially in the context of this problem.
  1. Describe the problem-solving approach that would lead from the problem statement to the final solution. Starting from the initial point (sx, sy), we need to determine if we can reach the target point (tx, ty) by performing a series of operations. The operation we can perform depends on whether tx or ty is larger, so we use a while loop and if-else conditions to continuously reduce tx and ty until they are not both larger than sx and sy. Once the loop ends, we check if we have reached a valid endpoint. If sx and tx are equal and sy is less than or equal to ty (with the difference being a multiple of sx), or if sy and ty are equal and sx is less than or equal to tx (with the difference being a multiple of sy), then we have reached the target point and return True. Otherwise, we return False.

Targeted Drills in Python

Concept 1: Basic Loop Structure

In Python, we use while and for loops to iterate over a block of code multiple times. Here’s an example of a while loop:

1
2
3
4

i = 0
while i < 5:
    print(i)
    i += 1

Concept 2: Conditional Statements

Conditional statements in Python use the if, elif, and else keywords to control the flow of the program based on certain conditions. Here’s an example:

1
2
3
4
5
6
7

x = 10
if x < 0:
    print("Negative number")
elif x == 0:
    print("Zero")
else:
    print("Positive number")

Concept 3: Modulo operation

Modulo operation returns the remainder of a division. In Python, it’s represented by the % operator. Here’s an example:

1

print(10 % 3)  # Output: 1

Problem-specific Concept: Backtracking in the context of the problem

The problem requires us to track back from the target point to the start. This involves checking the validity of each step and using modulo operation. An illustrative drill would be:

1
2
3
4
5
6
7
8

tx = 9
ty = 5
while tx > 0 and ty > 0:
    if tx > ty:
        tx %= ty
    else:
        ty %= tx
    print(tx, ty)

Integrating the Concepts:

To solve the problem, we start by implementing the while loop to continuously check and update the target points until they can’t be reduced further. Inside the loop, we use an if-else statement to decide which target coordinate to reduce based on their relative sizes. We use the modulo operation for the actual reduction. Finally, we use another set of conditional statements after the loop to check if we’ve reached the starting point and return the result. Each of these drills directly translates into a part of the solution method reachingPoints.

Q&A

Here is my understanding on (ty - sy) % tx == 0

Lets take a simple case where only the y part changes sx = 2, sy = 3, tx = 2, ty = 11

The tree would look like 2,3 -> 2,5 -> 2,7 -> 2,9 -> 2,11

ty can be written as: ty = sy + n * sx (n = number of times we add sx, in this case its 4) ty - sy = n * sx (ty - sy) % sx = (n * sx) % sx (ty - sy) % sx = 0

Yes, your understanding is correct. In your example, the operation is being performed on the ‘y’ coordinate. You start from ‘sy’ and each time you add ‘sx’ to it, until you reach ’ty’. This can be done ’n’ times, where ’n’ is an integer.

In this specific case, ’n’ is indeed 4, as you correctly calculated. And you can certainly express ’ty’ as ‘sy + n * sx’, where ’n’ is the number of operations performed (i.e., how many times ‘sx’ is added to ‘sy’).

Then, subtracting ‘sy’ from both sides of the equation gives you ’ty - sy = n * sx’.

So, the left hand side, ’ty - sy’, should be a multiple of ‘sx’ for it to be possible to reach from ‘sy’ to ’ty’ through the given operation. This is precisely what ‘(ty - sy) % sx = 0’ checks. If ’ty - sy’ is a multiple of ‘sx’, the modulo operation will result in 0. If not, it means we cannot reach ’ty’ from ‘sy’ through the given operation, because ‘sx’ cannot be added to ‘sy’ an integer number of times to get ’ty’.

In essence, the expression ‘(ty - sy) % sx == 0’ is a way of checking whether ’ty’ can be reached from ‘sy’ by performing the operation ‘add sx to the current y-coordinate’ a certain number of times.

It is very important to find that we should find the answer from target to begin if we start from sx and sy there is two possibility sx + sy, sy / sx, sx + xy but if we start from target there is only one possibility if (tx > ty) tx - ty, ty else tx, ty -tx because the question say that all input are positive integer, so we must use the bigger one to subtract the smaller one

Yes, your observation is spot on. This problem is more straightforward to solve by working backward from the target to the start. The reason is the constraint that all inputs are positive integers and the operations that are allowed.

Since we can only perform operations (x, x+y) or (x+y, y) where x and y are coordinates of the current point, starting from (sx, sy) means we will have multiple paths to reach the target which will involve branching and can quickly become very complex to solve or it might lead to infinite loops.

On the other hand, if we start from the target (tx, ty), at any point in time, there is always only one valid operation we can perform: If tx>ty, we can only do tx = tx - ty (because ty cannot be greater than tx, thus we can’t perform ty = ty - tx), and similarly if ty>tx, we can only do ty = ty - tx. This will always lead us to a unique path back to (sx, sy).

So by performing the operations backward, we reduce the problem’s complexity significantly. We keep subtracting the smaller coordinate from the larger one until we either reach the starting point (return True) or overshoot it (return False). This approach leverages the mathematical properties of the problem to provide a simpler and efficient solution.

Let d = gcd(sx, sy). Then by Bezout’s Identity, d divides all linear combinations of sx and sy. Note that, for the answer to be true, tx and ty must both be linear combinations of sx and ty. Therefore d must divide tx and ty. Then if d divides tx and d divides ty, answer is true. Else, false.

This doesn’t work when I coded it though. Why?

The logic you’re attempting to apply here relates to the properties of Bezout’s Identity. However, there’s a misunderstanding of how to apply it to this problem.

Bezout’s Identity states that for any two integers ‘a’ and ‘b’, there exist integers ‘x’ and ‘y’ such that ax + by = gcd(a, b). In your approach, you’re trying to find some ‘x’ and ‘y’ such that sxx + syy = tx (or ty). Although it’s valid to say that if tx and ty are multiples of gcd(sx, sy), they can be expressed as a linear combination of sx and sy, it’s not enough to solve this problem.

The operations allowed in this problem are more restrictive, as the transformations allowed are (x, x+y) or (x+y, y). We’re not merely looking for a linear combination of sx and sy. This means that sx and sy are not merely coefficients that can be multiplied by some integer and added to match tx and ty. Rather, they represent values that we can only add to each other in a specific way defined by the problem. We’re only allowed to add the current values of x and y, and these values are changing after each operation.

For these reasons, while Bezout’s Identity is a fascinating and relevant mathematical concept, it does not provide a direct solution to this problem. The problem’s constraints are more specific and don’t match the conditions under which Bezout’s Identity applies. The approach you should use for this problem is to work backward from the target, as mentioned before.

Am I the only one think modulo operations really confusing? This might help. Let’s start from (sx, sy), going forward to (tx, ty), step by step. Step 0: (x, y)

Step 1: We can do either (x+y, y) or (x, x+y) m1 times. The result can be either (x+m1 * y, y) or (x, m1 * x+y) Here m1 denotes number of moves at step N. m1 is a positive integer.

Step 2: We took m2 moves at Step2, starting from Step 1. The result can be (x+m1 * y, y) => (x+(m1+m2) * y, y) => (x+m1 * y, m2 * (x+m1 * y)+y) (x, m1 * x+y) => (x, (m1+m2) * x+y) => (x + m2 * (m1 * x + y), y) Since m1 is positive integer, (m1+m2) is covered by m1, we remove the first and third transform. (x+m1 * y, y) => (x+m1 * y, m2 * (x+m1 * y)+y) (x, m1 * x+y) => (x + m2 * (m1 * x + y), y) Let’s simplify the notation. (x1, y1) => (x1, m2 * x1 + y1) (x1, y1) => (x1 + m2 * y1, y1) Here x1, y1 is the result of Step 1. We can find that transfroms are taken alternatively, first m1 moves of (x+y, y), then m2 moves of (x, x+y). (Or (x, x+y), then (x+y, x).

Step 3: We can deduce that (x2, y2) => (x2, m3 * x2 + y2) (x2, y2) => (x2 + m3 * y2, y2) Here x2, y2 is the result of Step 2.

And so on til step N, (xn, yn) = (tx, ty).

We can find the steps are reversible. (x3, y3) = (x2 + m3 * y2, y2) => (x2, y2) where x2 = x3 % y3 ; y3 = y2 if x3 > y3 or (x3, y3) =(x2, m3 * x2 + y2) => (x2, y2) where y2 = y3 % x3 ; x3 = x2 if y3 > x3

We can do all the way down to Step 0, and even Step -1, -2, -3…. (if gcd(sx, sy) != 0) (sx, sy) will be in one of the reversing steps.

You’re correct in pointing out the concept of reversibility and the use of the modulo operation here. By taking the problem and working backwards from the end point (tx, ty) towards the start point (sx, sy), you can leverage the modulo operation to perform the inverse of the operation (x+y, y) or (x, x+y) as many times as needed. The modulo operation essentially reverses the addition that was performed to get to the target.

The modulo operation might be confusing because it involves division and remainder calculations, and in the context of this problem, it’s being used to reverse an addition operation. Here’s a simple way to think about it:

  • When you see (tx, ty) = (x + m * y, y), what it’s really saying is that you’ve added ‘y’ to ‘x’ a certain number of times (m times) to get to tx. So, to reverse this, you want to find out how many times ‘y’ was added to ‘x’, and this is exactly what tx % ty gives you.

Here’s how it can be coded in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        while sx < tx and sy < ty:
            if tx < ty:
                ty %= tx
            else:
                tx %= ty

        if sx == tx and sy <= ty and (ty - sy) % sx == 0:
            return True
        if sy == ty and sx <= tx and (tx - sx) % sy == 0:
            return True
        
        return False

In the above Python code, we begin with the target point (tx, ty) and reduce it using the modulo operation until we either reach the start point (sx, sy) or we can’t continue. The while loop handles the case where both tx and ty are larger than sx and sy, and the modulo operation ensures that we’re correctly reversing the operation (x, x+y) or (x+y, y). The two if statements handle the cases where we’ve reduced one of the coordinates (tx or ty) to match one of the starting coordinates (sx or sy). The conditions check that the remaining coordinate is greater than or equal to the remaining starting coordinate, and that the difference between them is divisible by the starting coordinate that has already been matched.

what if the point we want to manipulate on is not restricted to the 1st quadrant?, what if the points can be at all quadrants?, which means all int32.MinValue < x < int32.MaxValue, int32.MinValue < y < int32MaxValue? in this circumstance, the backward searching path is not unique for target point.

That’s a very astute observation!

In the original problem, we have an advantage because both the target and the starting points are in the first quadrant where all numbers are positive integers. This makes the path from the start to the target unique under the operation rules provided, and it also makes the process of reversing these operations straightforward.

However, if the points could be located in any of the four quadrants, the problem would indeed become much more complicated due to the presence of negative numbers. For instance, consider the operation of adding the y-coordinate to the x-coordinate: (x, y) => (x + y, y). If y is negative, this operation would effectively decrease the x-coordinate rather than increasing it. This could create multiple paths to reach the target point, and you would need a strategy to explore these possible paths effectively.

One way to handle this might be to use a breadth-first search (BFS) or depth-first search (DFS) algorithm starting from the initial point and exploring all possible next steps, until you either reach the target point or have checked all possible points. However, this approach could potentially be very time-consuming due to the large range of possible x and y values.

A better approach might be to consider the geometry of the problem and try to define some heuristic rules to guide the search process, but this would likely depend on the specific details of how the allowed operations work with negative numbers.