Dados dos números enteros A y B que representan las coordenadas de un punto en el primer cuadrante, la tarea es encontrar el número mínimo de pasos necesarios para llegar al origen. Todos los movimientos posibles desde un punto (i, j) son (i – 1, j), (i, j – 1) o (i, j) ( permanecer en la misma posición ).
Nota: No está permitido moverse en la misma dirección dos veces seguidas.
Ejemplos:
Entrada: A = 4, B = 0
Salida: 7
Explicación:
A continuación se muestran los movimientos desde los puntos dados hasta el origen:
(4, 0) → (3, 0) → (3, 0)(permanece) → (2, 0 ) → (2, 0)(permanece) → (1, 0) → (1, 0)(permanece) → (0, 0).
Por lo tanto, se requieren 7 movimientos para llegar al origen.Entrada: A = 3, B = 5
Salida: 9
Explicación:
A continuación se muestran los movimientos desde los puntos dados hasta el origen:
(3, 5) → (3, 4) → (2, 4) → (2, 3) → ( 1, 3) → (1, 2) → (0, 2) → (0, 1) → (0, 1) (permanece) → (0, 0).
Por lo tanto, se requieren 9 movimientos para llegar al origen.
Enfoque ingenuo: el enfoque más simple es la recursividad . La idea es considerar recursivamente todos los movimientos posibles desde cada punto y, para cada uno de ellos, calcular el número mínimo de pasos necesarios para llegar al origen.
Complejidad de Tiempo: O(3 max(A, B) )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en la observación de que si la diferencia absoluta entre las coordenadas x e y es 1 o 0 , entonces el número mínimo de pasos necesarios para llegar al origen es (a + b) . De lo contrario, toma (2 * abs(a – b) – 1) movimientos para alcanzar (k, k) , donde k es el mínimo de a, b .
Por lo tanto, el número mínimo de pasos necesarios para llegar al origen desde (a, b) es igual a = (Pasos necesarios para llegar a (k, k) + Pasos necesarios para llegar a (0, 0) desde (k, k)) = ( 2 * abs(a – b) – 1) + (2 * k)
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, ans , que almacena el número mínimo de pasos necesarios para llegar al origen desde (a, b) .
- Si la diferencia absoluta de a y b es 1 o 0 , actualice ans a (a + b) .
- De lo contrario:
- Encuentre el mínimo de a, b y guárdelo en una variable k .
- Usando la fórmula, actualice ans = (2 * abs(a – b) – 1) + (2 * k) .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum moves
// required to reach origin from (a, b)
void findMinMoves(int a, int b)
{
// Stores the minimum number of moves
int ans = 0;
// Check if the absolute
// difference is 1 or 0
if (a == b || abs(a - b) == 1) {
ans = a + b;
}
else {
// Store the minimum of a, b
int k = min(a, b);
// Store the maximum of a, b
int j = max(a, b);
ans = 2 * k + 2 * (j - k) - 1;
}
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
// Given co-ordinates
int a = 3, b = 5;
// Function Call
findMinMoves(a, b);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to find the minimum moves
// required to reach origin from (a, b)
static void findMinMoves(int a, int b)
{
// Stores the minimum number of moves
int ans = 0;
// Check if the absolute
// difference is 1 or 0
if (a == b || Math.abs(a - b) == 1)
{
ans = a + b;
}
else
{
// Store the minimum of a, b
int k = Math.min(a, b);
// Store the maximum of a, b
int j = Math.max(a, b);
ans = 2 * k + 2 * (j - k) - 1;
}
// Print the answer
System.out.print(ans);
}
// Driver Code
public static void main (String[] args)
{
// Given co-ordinates
int a = 3, b = 5;
// Function Call
findMinMoves(a, b);
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python3 program for the above approach # function to find the minimum moves # required to reach origin from (a, b) def findMinMoves(a, b): # Stores the minimum number of moves ans = 0 # Check if the absolute # difference is 1 or 0 if (a == b or abs(a - b) == 1): ans = a + b else: # Store the minimum of a, b k = min(a, b) # Store the maximum of a, b j = max(a, b) ans = 2 * k + 2 * (j - k) - 1 # Print the answer print (ans) # Driver Code if __name__ == '__main__': # Given co-ordinates a,b = 3, 5 # Function Call findMinMoves(a, b) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the minimum moves
// required to reach origin from (a, b)
static void findMinMoves(int a, int b)
{
// Stores the minimum number of moves
int ans = 0;
// Check if the absolute
// difference is 1 or 0
if (a == b || Math.Abs(a - b) == 1)
{
ans = a + b;
}
else
{
// Store the minimum of a, b
int k = Math.Min(a, b);
// Store the maximum of a, b
int j = Math.Max(a, b);
ans = 2 * k + 2 * (j - k) - 1;
}
// Print the answer
Console.Write(ans);
}
// Driver Code
public static void Main()
{
// Given co-ordinates
int a = 3, b = 5;
// Function Call
findMinMoves(a, b);
}
}
// This code is contributed by chitranayal.
Javascript
<script>
// JavaScript program to implement the above approach
// Function to find the minimum moves
// required to reach origin from (a, b)
function findMinMoves(a, b)
{
// Stores the minimum number of moves
let ans = 0;
// Check if the absolute
// difference is 1 or 0
if (a == b || Math.abs(a - b) == 1) {
ans = a + b;
}
else {
// Store the minimum of a, b
let k = Math.min(a, b);
// Store the maximum of a, b
let j = Math.max(a, b);
ans = 2 * k + 2 * (j - k) - 1;
}
// Print the answer
document.write(ans);
}
// Driver Code
// Given co-ordinates
let a = 3, b = 5;
// Function Call
findMinMoves(a, b);
</script>
9
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA