[20 Feb 2020] Check if it is possible to move from (0, 0) to (X, Y) in exactly K steps

Check if it is possible to move from (0, 0) to (X, Y) in exactly K steps
Given a point (X, Y) in a 2-D plane and an integer K, the task is to check whether it is possible to move from (0, 0) to the given point (X, Y) in exactly K moves. In a single move, the positions that are reachable from (X, Y) are (X, Y + 1), (X, Y – 1), (X + 1, Y) and (X – 1, Y).

Examples:

Input: X = 0, Y = 0, K = 2
Output: Yes
Move 1: (0, 0) -> (0, 1)
Move 2: (0, 1) -> (0, 0)

Input: X = 5, Y = 8, K = 20
Output: No

Approach: It is clear that the shortest path to reach (X, Y) from (0, 0) will be minMoves = (|X| + |Y|). So, if K < minMoves then it is impossible to reach (X, Y) but if K ≥ minMoves then after reaching (X, Y) in minMoves number of moves the remaining (K – minMoves) number of moves have to be even in order to remain at that point for the rest of the moves.
So it is possible to reach (X, Y) from (0, 0) only if K ≥ (|X| + |Y|) and (K – (|X| + |Y|)) % 2 = 0.

Below is the implementation of the above approach:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if it is
// possible to move from (0, 0) to
// (x, y) in exactly k moves
bool isPossible(int x, int y, int k)
{
    // Minimum moves required
    int minMoves = abs(x) + abs(y);
 
    // If possible
    if (k >= minMoves && (k - minMoves) % 2 == 0)
        return true;
 
    return false;
}
 
// Driver code
int main()
{
    int x = 5, y = 8, k = 20;
 
    if (isPossible(x, y, k))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}
Output:
No

// Java implementation of the approach 

class GFG

{

      

    // Function that returns true if it is 

    // possible to move from (0, 0) to 

    // (x, y) in exactly k moves 

    static boolean isPossible(int x, int y, int k) 

    { 

        // Minimum moves required 

        int minMoves = Math.abs(x) + Math.abs(y); 

      

        // If possible 

        if (k >= minMoves && (k - minMoves) % 2 == 0) 

            return true; 

      

        return false; 

    } 

      

    // Driver code 

    public static void main (String[] args) 

    { 

        int x = 5, y = 8, k = 20; 

      

        if (isPossible(x, y, k)) 

            System.out.println("Yes"); 

        else

            System.out.println("No"); 

    } 

}

  

# Python3 implementation of the approach

  

# Function that returns true if it is

# possible to move from (0, 0) to

# (x, y) in exactly k moves

def isPossible(x, y, k):

      

    # Minimum moves required

    minMoves = abs(x) + abs(y)

  

    # If possible

    if (k >= minMoves and (k - minMoves) % 2 == 0):

        return True

  

    return False

  

# Driver code

x = 5

y = 8

k = 20

  

if (isPossible(x, y, k)):

    print("Yes")

else:

    print("No")