Compruebe si se puede obtener N de 0 utilizando como máximo X incrementos y como máximo Y operaciones de duplicación

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 = 24

Entrada: 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>
Producción

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *