Dados dos números enteros positivos X e Y , la tarea es encontrar si se puede llegar a un punto (X, Y) desde el punto (0, 0) tal que en cada i-ésimo movimiento, la coordenada x o la coordenada y se pueda incrementar en 3 yo _ Si es posible, imprima Sí . De lo contrario , imprima No.
Ejemplos:
Entrada: X = 1, Y = 3
Salida: Sí
Explicación:
Los siguientes son los pasos de (0, 0) a (1, 3):Paso 0: Incrementar la coordenada X en 3 0 (= 1) modifica las coordenadas a (1, 0).
Paso 1: Incrementar la coordenada Y en 3 1 (= 2) modifica las coordenadas a (1, 3).Por lo tanto, las coordenadas (1, 3) se pueden alcanzar desde (0, 0). Por lo tanto, imprima Sí.
Entrada: X = 10, Y = 30
Salida: Sí
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los movimientos posibles desde (X, Y) al disminuir 3 i en cada i-ésimo paso y verificar si alguna de esas combinaciones de movimientos alcanza (0, 0) o no. Si es posible, imprima Sí . De lo contrario , imprima No.
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 whether (0, 0) can
// be reached from (X, Y) by decrementing
// 3^i at each ith step
bool canReach(int X, int Y, int steps)
{
// Termination Condition
if (X == 0 && Y == 0) {
return true;
}
if (X < 0 || Y < 0) {
return false;
}
// Otherwise, recursively call by
// decrementing 3^i at each step
return (
canReach(X - (int)pow(3, steps),
Y, steps + 1)
| canReach(X, Y - (int)pow(3, steps),
steps + 1));
}
// Driver Code
int main()
{
int X = 10, Y = 30;
if (canReach(X, Y, 0)) {
cout << "YES" << endl;
}
else
cout << "NO" << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find whether (0, 0) can
// be reached from (X, Y) by decrementing
// 3^i at each ith step
static boolean canReach(int X, int Y, int steps)
{
// Termination Condition
if (X == 0 && Y == 0) {
return true;
}
if (X < 0 || Y < 0) {
return false;
}
// Otherwise, recursively call by
// decrementing 3^i at each step
return (
canReach(X - (int)Math.pow(3, steps),
Y, steps + 1)
| canReach(X, Y - (int)Math.pow(3, steps),
steps + 1));
}
// Driver Code
public static void main(String[] args)
{
int X = 10, Y = 30;
if (canReach(X, Y, 0)) {
System.out.print("YES" +"\n");
}
else
System.out.print("NO" +"\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python 3 program for the above approach
# Function to find whether (0, 0) can
# be reached from (X, Y) by decrementing
# 3^i at each ith step
def canReach(X, Y, steps):
# Termination Condition
if (X == 0 and Y == 0):
return True
if (X < 0 or Y < 0):
return False
# Otherwise, recursively call by
# decrementing 3^i at each step
return (canReach(X - int(pow(3, steps)),Y, steps + 1)| canReach(X, Y - int(pow(3, steps)),steps + 1))
# Driver Code
if __name__ == '__main__':
X = 10
Y = 30
if(canReach(X, Y, 0)):
print("YES")
else:
print("NO")
# This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find whether (0, 0) can
// be reached from (X, Y) by decrementing
// 3^i at each ith step
static Boolean canReach(int X, int Y, int steps)
{
// Termination Condition
if (X == 0 && Y == 0) {
return true;
}
if (X < 0 || Y < 0) {
return false;
}
// Otherwise, recursively call by
// decrementing 3^i at each step
return (
canReach(X - (int)Math.Pow(3, steps),
Y, steps + 1)
| canReach(X, Y - (int)Math.Pow(3, steps),
steps + 1));
}
// Driver Code
public static void Main(String[] args)
{
int X = 10, Y = 30;
if (canReach(X, Y, 0)) {
Console.Write("YES" +"\n");
}
else
Console.Write("NO" +"\n");
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program for the above approach
// Function to find whether (0, 0) can
// be reached from (X, Y) by decrementing
// 3^i at each ith step
function canReach(X, Y, steps) {
// Termination Condition
if (X == 0 && Y == 0) {
return true;
}
if (X < 0 || Y < 0) {
return false;
}
// Otherwise, recursively call by
// decrementing 3^i at each step
return (
canReach(X - Math.pow(3, steps), Y, steps + 1) |
canReach(X, Y - Math.pow(3, steps), steps + 1)
);
}
// Driver Code
let X = 10,
Y = 30;
if (canReach(X, Y, 0)) {
document.write("YES");
} else document.write("NO");
// This code is contributed by gfgking.
</script>
Producción:
YES
Complejidad Temporal: O(2 K ), donde K es el número máximo de pasos realizados.
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones al convertir X e Y en base 3:
- Si hay 1 tanto en el valor de X como en el de Y en base 3, entonces (X, Y) no se puede alcanzar ya que este paso no se puede realizar en ambas direcciones.
- Si hay 2 en cualquier valor de X e Y en base 3, entonces (X, Y) no se puede alcanzar ya que esto no se puede representar en la potencia perfecta de 3 .
- Si hay 0 en cualquier valor de X e Y en base 3, entonces (X, Y) no se puede alcanzar ya que este paso no se puede realizar excepto el último paso.
- De lo contrario, en todos los casos restantes (X, Y) se puede llegar desde (0, 0).
A partir de las observaciones anteriores, imprima el resultado en consecuencia.
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 whether (0, 0) can
// be reached from (X, Y) by decrementing
// 3^i at each ith step
bool canReach(int X, int Y)
{
// Stores the number of steps
// performed to reach (X, Y)
int steps = 0;
while (X || Y) {
// Value of X in base 3
int pos1 = X % 3;
// Value of Y in base 3
int pos2 = Y % 3;
// Check if any has value 2
if (pos1 == 2 || pos2 == 2) {
return false;
}
// If both have value 1
if (pos1 == 1 && pos2 == 1) {
return false;
}
// If both have value 0
if (pos1 == 0 && pos2 == 0) {
return false;
}
X /= 3;
Y /= 3;
steps++;
}
// Otherwise, return true
return true;
}
// Driver Code
int main()
{
int X = 10, Y = 30;
if (canReach(X, Y)) {
cout << "YES";
}
else {
cout << "NO";
}
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to find whether (0, 0) can
// be reached from (X, Y) by decrementing
// 3^i at each ith step
static boolean canReach(int X, int Y)
{
// Stores the number of steps
// performed to reach (X, Y)
int steps = 0;
while (X != 0 || Y != 0) {
// Value of X in base 3
int pos1 = X % 3;
// Value of Y in base 3
int pos2 = Y % 3;
// Check if any has value 2
if (pos1 == 2 || pos2 == 2) {
return false;
}
// If both have value 1
if (pos1 == 1 && pos2 == 1) {
return false;
}
// If both have value 0
if (pos1 == 0 && pos2 == 0) {
return false;
}
X /= 3;
Y /= 3;
steps++;
}
// Otherwise, return true
return true;
}
// Driver Code
public static void main(String[] args)
{
int X = 10, Y = 30;
if (canReach(X, Y)) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
}
}
// This code is contributed by Potta Lokesh
Python3
# Python program for the above approach
# Function to find whether (0, 0) can
# be reached from (X, Y) by decrementing
# 3^i at each ith step
def canReach(X, Y):
# Stores the number of steps
# performed to reach (X, Y)
steps = 0
while (X != 0 or Y != 0):
# Value of X in base 3
pos1 = X % 3
# Value of Y in base 3
pos2 = Y % 3
# Check if any has value 2
if (pos1 == 2 or pos2 == 2):
return False
# If both have value 1
if (pos1 == 1 and pos2 == 1):
return False
# If both have value 0
if (pos1 == 0 and pos2 == 0):
return False
X /= 3
Y /= 3
steps += 1
# Otherwise, return true
return True
# Driver Code
X = 10
Y = 30
if (canReach(X, Y)):
print("YES")
else:
print("NO")
# This code is contributed by _saurabh_jaiswal
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to find whether (0, 0) can
// be reached from (X, Y) by decrementing
// 3^i at each ith step
static bool canReach(int X, int Y)
{
// Stores the number of steps
// performed to reach (X, Y)
int steps = 0;
while (X != 0 || Y != 0) {
// Value of X in base 3
int pos1 = X % 3;
// Value of Y in base 3
int pos2 = Y % 3;
// Check if any has value 2
if (pos1 == 2 || pos2 == 2) {
return false;
}
// If both have value 1
if (pos1 == 1 && pos2 == 1) {
return false;
}
// If both have value 0
if (pos1 == 0 && pos2 == 0) {
return false;
}
X /= 3;
Y /= 3;
steps++;
}
// Otherwise, return true
return true;
}
// Driver Code
public static void Main(String[] args)
{
int X = 10, Y = 30;
if (canReach(X, Y)) {
Console.WriteLine("YES");
}
else {
Console.WriteLine("NO");
}
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// javascript program for the above approach
// Function to find whether (0, 0) can
// be reached from (X, Y) by decrementing
// 3^i at each ith step
function canReach(X , Y)
{
// Stores the number of steps
// performed to reach (X, Y)
var steps = 0;
while (X != 0 || Y != 0) {
// Value of X in base 3
var pos1 = X % 3;
// Value of Y in base 3
var pos2 = Y % 3;
// Check if any has value 2
if (pos1 == 2 || pos2 == 2) {
return false;
}
// If both have value 1
if (pos1 == 1 && pos2 == 1) {
return false;
}
// If both have value 0
if (pos1 == 0 && pos2 == 0) {
return false;
}
X /= 3;
Y /= 3;
steps++;
}
// Otherwise, return true
return true;
}
// Driver Code
var X = 10, Y = 30;
if (canReach(X, Y)) {
document.write("YES");
}
else {
document.write("NO");
}
// This code contributed by shikhasingrajput
</script>
Producción:
YES
Complejidad de tiempo: O(log 3 (max(X, Y))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA