Dados tres números enteros N , X e Y , la tarea es verificar si N se puede obtener de 0 usando las siguientes operaciones:
- El entero actual se puede incrementar en uno (es decir, x = x + 1) y esto se puede hacer como máximo X veces .
- Duplique el número entero actual (es decir, x = 2 * x) y esto se puede hacer como máximo Y veces .
Devuelve falso si no se puede localizar el número.
Ejemplos:
Entrada: N = 24, X = 6 ,Y = 2
Salida: verdadero
Explicación: Inicialmente, a = 0
Incremento una vez así a = 1
Incremento una vez así a = 2
Incremento una vez así a = 3
Incremento una vez así a = 4
Incremento una vez así a = 5
Incrementar una vez así a = 6
Doble una vez así a = 12
Doble de nuevo así a = 24Entrada: N = 4, X = 2, Y = 0
Salida: falso
Enfoque: la pregunta también se puede considerar en el escenario exactamente opuesto, donde se da N y necesitamos reducirlo a 0 usando dos operaciones:
- Dividiendo el objetivo por 2 tantos como maxDoubles veces
- Decrementando el objetivo en 1 tanto como maxadd veces.
Use la función recursiva de esta manera para verificar si se puede obtener 0 o no. En cada escenario recursivo, disminuya 1 y vuelva a llamar a la función. Y si el número es par, divídalo por 2 y llame a la función recursiva. Si se puede obtener 0 dentro del límite dado de movimientos, devuelve verdadero. De lo contrario, devuelve falso.
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 check if N is reached
bool checktogetTarget(int N, int X, int Y)
{
// If N is already zero return true
if (N == 0)
return true;
// If can't double and increment,
// just return false
if (Y == 0 && X == 0)
return false;
int temp = N;
while (1) {
// If N is not divisible by 2,
// then just decrement it by 1
if (temp % 2 == 0 && Y != 0) {
temp = temp / 2;
Y--;
}
else if (X != 0) {
temp--;
X--;
}
if (temp == 0)
break;
if (Y == 0 && X == 0)
break;
}
// if temp becomes 0 after
// performing operation
if (temp == 0) {
return true;
}
else {
return false;
}
}
// Driver Code
int main()
{
int N = 24;
int X = 6;
int Y = 2;
bool ans = checktogetTarget(N, X, Y);
if (ans)
cout << "true";
else
cout << "false";
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to check if N is reached
static Boolean checktogetTarget(int N, int X, int Y)
{
// If N is already zero return true
if (N == 0)
return true;
// If can't double and increment,
// just return false
if (Y == 0 && X == 0)
return false;
int temp = N;
while (true) {
// If N is not divisible by 2,
// then just decrement it by 1
if (temp % 2 == 0 && Y != 0) {
temp = temp / 2;
Y--;
}
else if (X != 0) {
temp--;
X--;
}
if (temp == 0)
break;
if (Y == 0 && X == 0)
break;
}
// if temp becomes 0 after
// performing operation
if (temp == 0) {
return true;
}
else {
return false;
}
}
// Driver Code
public static void main (String[] args) {
int N = 24;
int X = 6;
int Y = 2;
Boolean ans = checktogetTarget(N, X, Y);
if (ans)
System.out.print("true");
else
System.out.print("false");
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python code for the above approach
# Function to check if N is reached
def checktogetTarget(N, X, Y):
# If N is already zero return true
if (N == 0):
return True;
# If can't double and increment,
# just return false
if (Y == 0 and X == 0):
return False;
temp = N;
while (1):
# If N is not divisible by 2,
# then just decrement it by 1
if (temp % 2 == 0 and Y != 0):
temp = temp / 2;
Y -= 1
elif (X != 0):
temp -= 1
X -= 1
if (temp == 0):
break;
if (Y == 0 and X == 0):
break;
# if temp becomes 0 after
# performing operation
if (temp == 0):
return True
else:
return False
# Driver Code
N = 24;
X = 6;
Y = 2;
ans = checktogetTarget(N, X, Y);
if (ans):
print("true");
else:
print("false");
# This code is contributed by Saurabh Jaiswal
C#
// C# program for above approach
using System;
class GFG
{
// Function to check if N is reached
static bool checktogetTarget(int N, int X, int Y)
{
// If N is already zero return true
if (N == 0)
return true;
// If can't double and increment,
// just return false
if (Y == 0 && X == 0)
return false;
int temp = N;
while (true) {
// If N is not divisible by 2,
// then just decrement it by 1
if (temp % 2 == 0 && Y != 0) {
temp = temp / 2;
Y--;
}
else if (X != 0) {
temp--;
X--;
}
if (temp == 0)
break;
if (Y == 0 && X == 0)
break;
}
// if temp becomes 0 after
// performing operation
if (temp == 0) {
return true;
}
else {
return false;
}
}
// Driver Code
public static void Main()
{
int N = 24;
int X = 6;
int Y = 2;
bool ans = checktogetTarget(N, X, Y);
if (ans)
Console.Write("true");
else
Console.Write("false");
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to check if N is reached
function checktogetTarget(N, X, Y) {
// If N is already zero return true
if (N == 0)
return true;
// If can't double and increment,
// just return false
if (Y == 0 && X == 0)
return false;
let temp = N;
while (1) {
// If N is not divisible by 2,
// then just decrement it by 1
if (temp % 2 == 0 && Y != 0) {
temp = temp / 2;
Y--;
}
else if (X != 0) {
temp--;
X--;
}
if (temp == 0)
break;
if (Y == 0 && X == 0)
break;
}
// if temp becomes 0 after
// performing operation
if (temp == 0) {
return true;
}
else {
return false;
}
}
// Driver Code
let N = 24;
let X = 6;
let Y = 2;
let ans = checktogetTarget(N, X, Y);
if (ans)
document.write("true");
else
document.write("false");
// This code is contributed by Potta Lokesh
</script>
true
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sauarbhyadav y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA