Check if the player can reach the target co-ordinates after performing given moves from origin

Given an array arr[] of size N describing N moves. A player standing at origin (0, 0). In the first move, the player can move either right or left by distance arr[1]. In the second move, the player can move up or down by distance arr[2], In the third move player can move left or right by distance arr[3], and so on till arr[N]. That is on odd moves player moves along the X coordinate and on even moves, the player moves along the Y coordinate. The task for this problem is to check whether coordinate (X, Y) is reachable from (0, 0) if the player performs these moves optimally. If this is possible print “Yes” else print “No”. 

Examples : 

Input: A[] = {2, 1, 3}, X = -1, Y = 1
Output: Yes
Explanation:

Example 1

Following is one of the possible ways to  reach at (-1, 1)

• In first move player moves to (2, 0) by moving along positive direction of X co-ordinate by distance 2
• In second move player moves to (2, 1) by moving along positive direction of Y co-ordinate by distance 1
• In Third move player moves to (-1, 1) by moving along negative direction of X co-ordinate by distance 3

Input: A[] = {1, 2, 3, 4}, X = 5, Y = 5
Output: No

Naive approach: The basic way to solve the problem is as follows:

Visiting all possible co-ordinates by recursive brute force in exponential time. 

Complexity Analysis:
Time Complexity: O(2^N)
Auxiliary Space: O(1)

Efficient Approach:  The above approach can be optimized based on the following idea

Important observation is that this problem can independently solved for both coordinates X and Y.

Lets reduce this problem to 1 dimension. Players starts from 0.

• Problem 1: Player has to reach on coordinate X by following moves {A[1], A[3], A[5], …….} on each move player can move back and forth by distance A[i].
• Problem 2: Player has to reach on coordinate Y by following moves {A[2], A[4], A[6], ……..} on each move player can move back and forth by distance A[i].

Dynamic programming can be used to solve this problem for each independent coordinate.

• dp[i][j] is either True or False, represents whether coordinate j is reachable or not in first i moves. 
• recurrence relation : dp[i][j] = max(dp[i + 1][j + A[i]], dp[i + 1][j – A[i]])

it can be observed that there are N * A_Max states but the recursive function is called exponential times. That means that some states are called repeatedly. So the idea is to store the value of states. This can be done using recursive structure intact and just store the value in a HashMap and whenever the function is called, return the value store without computing 

• if both X and Y coordinates are reachable independently then coordinate (X, Y) is also reachable for player.

Follow the steps below to solve the problem:

• Creating two different array A1[] and A2[] for two independent problems and calling recursive function recur() for both.
• Create a recursive function that takes two parameters i representing i’th move and j represents current coordinate.
• Call recursive function for both moving right or up and left or down.
• Check the base case  if at the end of Nth move we are on T which is target co-ordinate then return 1 else return 0.
• Create an 2d array of dp[501][10001] with initially filled with -1.
• If the answer for a particular state is computed then save it in dp[i][j].
• If the answer for a particular state is already computed then just return dp[i][j].
• Create two variables isPossibleX and isPossibleY for storing answer of two independent problems.
• If isPossibleX and isPossibleY both are 1 then print “Yes” else print “No”.

Below is the implementation of the above approach.

Yes
No

Complexity Analysis:
Time Complexity: O(N * A_Max) 
Auxiliary Space: O(N * A_Max)

Where A_Max is Maximum value in array A[]

Related Articles :

• Introduction to Dynamic Programming – Data Structures and Algorithms Tutorials

Commit to GfG’s Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.