Minimice los movimientos para alcanzar un punto de destino desde el origen moviéndose horizontal o diagonalmente en la dirección correcta

Dada la fuente (X1, Y1) como (0, 0) y un objetivo (X2, Y2) en un plano 2-D. En un solo paso, se puede visitar (X1+1, Y1+1) o (X1+1, Y1) desde (X1, Y1) . La tarea es calcular los movimientos mínimos necesarios para alcanzar el objetivo utilizando los movimientos dados. Si no se puede alcanzar el objetivo, imprima “-1” .

Ejemplos: 

Entrada: X2 = 1, Y2 = 0
Salida: 1
Explicación: Tome 1 paso de (X1, Y1) a (X1+1, Y1), es decir, (0,0) -> (1,0). Entonces, el número de movimientos para alcanzar el objetivo es 1.

Entrada: X2 = 47, Y2 = 11
Salida:  47

Enfoque ingenuo: el enfoque ingenuo para resolver este problema es comprobar todas las combinaciones de (X+1, Y) y (X+1, Y+1) movimientos necesarios para alcanzar el objetivo e imprimir el mínimo entre ellos.

Enfoque eficiente: en función de las condiciones dadas sobre el movimiento, se pueden observar los siguientes puntos:

• Si Y2 > X2, entonces no podemos el objetivo ya que en cada movimiento debe aumentar X en 1.
• Si Y2 < X2, entonces podemos movernos diagonalmente Y2 veces y luego (X2-Y2) veces horizontalmente, o viceversa.
• Si Y2 = X2, entonces podemos mover X2 veces en diagonal o Y2 se mueve en diagonal

La tarea se puede resolver utilizando las observaciones anteriores. Si Y2 > X2 , entonces nunca se puede alcanzar el objetivo con los movimientos dados, de lo contrario, siempre es necesario un mínimo de X2 movimientos . 

A continuación se muestra la implementación del enfoque anterior:

// C++ Implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum moves
int minimum_Moves(int x, int y)
{
    // If y > x, target can never be reached
    if (x < y)
        return -1;
    // In all other case answer will be X
    else
        return x;
}
 
// Driver Code
int main()
{
    long long int X2 = 47, Y2 = 11;
    printf("%d", minimum_Moves(X2, Y2));
}
 
// This code is contributed by Sania Kumari Gupta

// C Implementation of the approach
#include <stdio.h>
 
// Function to find minimum moves
int minimum_Moves(int x, int y)
{
    // If y > x, target can never be reached
    if (x < y)
        return -1;
    // In all other case answer will be X
    else
        return x;
}
 
// Driver Code
int main()
{
    long long int X2 = 47, Y2 = 11;
    printf("%d", minimum_Moves(X2, Y2));
}
 
// This code is contributed by Sania Kumari Gupta

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to find minimum moves
  static long minimum_Moves(long x, long y)
  {
     
    // If y > x, target can never be reached
    if (x < y) {
      return -1;
    }
 
    // In all other case answer will be X
    else {
      return x;
    }
  }
 
  // Driver Code
  public static void main (String[] args)
  {
 
    long  X2 = 47, Y2 = 11;
    System.out.println(minimum_Moves(X2, Y2));
  }
}
 
// This code is contributed by hrithikgarg03188

# Pyhton Implementation of the approach
 
# Function to find minimum moves
def minimum_Moves(x, y):
     
    # If y > x, target can never be reached
    if (x < y):
        return -1
 
    # In all other case answer will be X
    else:
        return x
 
# Driver Code
X2 = 47
Y2 = 11
print(minimum_Moves(X2, Y2))
 
# This code is contributed by samim2000.

// C# Implementation of the approach
using System;
class GFG {
 
    // Function to find minimum moves
    static int minimum_Moves(int x, int y)
    {
       
        // If y > x, target can never be reached
        if (x < y) {
            return -1;
        }
 
        // In all other case answer will be X
        else {
            return x;
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int X2 = 47, Y2 = 11;
        Console.WriteLine(minimum_Moves(X2, Y2));
    }
}
 
// This code is contributed by ukasp.

<script>
       // JavaScript code for the above approach
 
       // Function to find minimum moves
       function minimum_Moves(x, y)
       {
        
           // If y > x, target can never be reached
           if (x < y)
           {
               return -1;
           }
 
           // In all other case answer will be X
           else
           {
               return x;
           }
       }
 
       // Driver Code
       let X2 = 47, Y2 = 11;
       document.write(minimum_Moves(X2, Y2) + '<br>');
 
        // This code is contributed by Potta Lokesh
   </script>

47

Complejidad de Tiempo : O(1)
Espacio Auxiliar : O(1)