Dada una array arr[] que consta de 4 enteros cada uno entre [1-9] , la tarea es comprobar si es posible obtener el número 24 colocando los operadores + , – , / y * entre los números o agrupándolos utilizando paréntesis. Si es posible, imprima » Posible «, de lo contrario imprima » No posible».
Ejemplos:
Entrada: arr[] = {3, 6, 8, 2}
Salida: Posible
explicación:
Una forma posible de obtener 24 es 3 × 6 + 8 – 2 = 24.Entrada: arr[] = {7, 2, 10, 6}
Salida: Posible
explicación:
Una forma posible de obtener 24 es (7 × 2–10) x 6 = 24.
Enfoque: La idea más simple para resolver este problema se basa en retroceder . Siga los pasos a continuación para resolver el problema:
- Cree una función, digamos isNumber24Possible(arr[]) y aplique las cuatro operaciones entre cada elemento consecutivo y llame recursivamente a la función digamos isNumber24PossibleUtil(op1, op2, op3) que realiza todas las operaciones posibles en 3 números.
- La función isNumber24PossibleUtil(op1, op2, op3) aplica las cuatro operaciones entre cada elemento consecutivo y llama a la función sobrecargada isNumber24PossibleUtil(op1, op2) que aplica la operación en 2 números.
- La función isNumber24PossibleUtil(op1, op2) se usa para verificar si los dos números dados pueden reducirse a 24 usando cualquiera de las 4 operaciones, es decir , + , – , / y * . Pruebe todas las operaciones entre los números, si alguno de ellos da como resultado 24 , devuelva verdadero ; de lo contrario, devuelva 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;
// Division operation might loose some
// precision consider 0.001 as tolerance.
#define TOLERANCE 0.001
// This function is used to check whether
// given two number can reduce to 24 using
// any of the 4 operations
bool isNumber24PossibleUtil(double op1, double op2)
{
// Check if any of the operation result to 24
if (abs(op1 + op2 - 24.0) < TOLERANCE
|| abs(op1 - op2 - 24.0) < TOLERANCE
|| abs(op1 * op2 - 24.0) < TOLERANCE
|| op2 && abs(op1 / op2 - 24.0) < TOLERANCE)
return true;
return false;
}
// Function which applies all the possible operations
// in between all the parameters and call the function
// which check if given number can result in 24 or not
bool isNumber24PossibleUtil(double op1, double op2, double op3)
{
// Applying operation between two operands reduces
// the count of operands to two
if (isNumber24PossibleUtil(op1 + op2, op3)
|| isNumber24PossibleUtil(op1 - op2, op3)
|| isNumber24PossibleUtil(op1 * op2, op3)
|| op2 && isNumber24PossibleUtil(op1 / op2, op3))
return true;
if (isNumber24PossibleUtil(op1, op2 + op3)
|| isNumber24PossibleUtil(op1, op2 - op3)
|| isNumber24PossibleUtil(op1, op2 * op3)
|| op3 && isNumber24PossibleUtil(op1, op2 / op3))
return true;
return false;
}
// Function takes given array as arr parameter
// and apply all possible operation in every
// consecutive elements and check if the remaining
// 3 parameters can be used for obtaining 24 or not
bool isNumber24Possible(int arr[])
{
// Apply every operation between first two operands
if (isNumber24PossibleUtil(arr[0] + arr[1], arr[2], arr[3])
|| isNumber24PossibleUtil(arr[0] - arr[1], arr[2], arr[3])
|| isNumber24PossibleUtil(arr[0] * arr[1], arr[2], arr[3])
|| arr[1] && isNumber24PossibleUtil(arr[0] / arr[1], arr[2], arr[3]))
return true;
// Between second and third operands
if (isNumber24PossibleUtil(arr[0], arr[1] + arr[2], arr[3])
|| isNumber24PossibleUtil(arr[0], arr[1] - arr[2], arr[3])
|| isNumber24PossibleUtil(arr[0], arr[1] * arr[2], arr[3])
|| arr[2] && isNumber24PossibleUtil(arr[0], arr[1] / arr[2], arr[3]))
return true;
// Between third and fourth operands
if (isNumber24PossibleUtil(arr[0], arr[1], arr[2] + arr[3])
|| isNumber24PossibleUtil(arr[0], arr[1], arr[2] - arr[3])
|| isNumber24PossibleUtil(arr[0], arr[1], arr[2] * arr[3])
|| arr[3] && isNumber24PossibleUtil(arr[0], arr[1], arr[2] / arr[3]))
return true;
return false;
}
// Driver Code
int main()
{
// Given Input
int arr[] = { 3, 6, 8, 2 };
// Function Call
if (isNumber24Possible(arr)) {
cout << "Possible" << endl;
}
else {
cout << "Not Possible" << endl;
}
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Division operation might loose some
// precision consider 0.001 as tolerance.
static double TOLERANCE = 0.001;
// This function is used to check whether
// given two number can reduce to 24 using
// any of the 4 operations
static boolean isNumber24PossibleUtil(double op1,
double op2)
{
// Check if any of the operation result to 24
if (Math.abs(op1 + op2 - 24.0) < TOLERANCE ||
Math.abs(op1 - op2 - 24.0) < TOLERANCE ||
Math.abs(op1 * op2 - 24.0) < TOLERANCE ||
op2 != 0 && Math.abs(op1 / op2 - 24.0) < TOLERANCE)
return true;
return false;
}
// Function which applies all the possible operations
// in between all the parameters and call the function
// which check if given number can result in 24 or not
static boolean isNumber24PossibleUtil(double op1, double op2,
double op3)
{
// Applying operation between two operands reduces
// the count of operands to two
if (isNumber24PossibleUtil(op1 + op2, op3) ||
isNumber24PossibleUtil(op1 - op2, op3) ||
isNumber24PossibleUtil(op1 * op2, op3) ||
op2 != 0 && isNumber24PossibleUtil(op1 / op2, op3))
return true;
if (isNumber24PossibleUtil(op1, op2 + op3) ||
isNumber24PossibleUtil(op1, op2 - op3) ||
isNumber24PossibleUtil(op1, op2 * op3) ||
op3 != 0 && isNumber24PossibleUtil(op1, op2 / op3))
return true;
return false;
}
// Function takes given array as arr parameter
// and apply all possible operation in every
// consecutive elements and check if the remaining
// 3 parameters can be used for obtaining 24 or not
static boolean isNumber24Possible(int arr[])
{
// Apply every operation between first two operands
if (isNumber24PossibleUtil(arr[0] + arr[1], arr[2], arr[3]) ||
isNumber24PossibleUtil(arr[0] - arr[1], arr[2], arr[3]) ||
isNumber24PossibleUtil(arr[0] * arr[1], arr[2], arr[3]) ||
arr[1] != 0 && isNumber24PossibleUtil(arr[0] / arr[1], arr[2],
arr[3]))
return true;
// Between second and third operands
if (isNumber24PossibleUtil(arr[0], arr[1] + arr[2], arr[3]) ||
isNumber24PossibleUtil(arr[0], arr[1] - arr[2], arr[3]) ||
isNumber24PossibleUtil(arr[0], arr[1] * arr[2], arr[3]) ||
arr[2] != 0 && isNumber24PossibleUtil(arr[0], arr[1] / arr[2],
arr[3]))
return true;
// Between third and fourth operands
if (isNumber24PossibleUtil(arr[0], arr[1], arr[2] + arr[3]) ||
isNumber24PossibleUtil(arr[0], arr[1], arr[2] - arr[3]) ||
isNumber24PossibleUtil(arr[0], arr[1], arr[2] * arr[3]) ||
arr[3] != 0 && isNumber24PossibleUtil(arr[0], arr[1],
arr[2] / arr[3]))
return true;
return false;
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int arr[] = { 3, 6, 8, 2 };
// Function Call
if (isNumber24Possible(arr))
{
System.out.print("Possible");
}
else
{
System.out.print("Not Possible");
}
}
}
// This code is contributed by code_hunt
Python3
# Python3 program for the above approach
# Division operation might loose some
# precision consider 0.001 as tolerance.
TOLERANCE = 0.001
# This function is used to check whether
# given two number can reduce to 24 using
# any of the 4 operations
def isNumber24PossibleUtill(op1, op2):
# Check if any of the operation result to 24
if (abs(op1 + op2 - 24.0) < TOLERANCE or
abs(op1 - op2 - 24.0) < TOLERANCE or
abs(op1 * op2 - 24.0) < TOLERANCE or
op2 and abs(op1 / op2 - 24.0) < TOLERANCE):
return True
return False
# Function which applies all the possible operations
# in between all the parameters and call the function
# which check if given number can result in 24 or not
def isNumber24PossibleUtil(op1, op2, op3):
# Applying operation between two operands reduces
# the count of operands to two
if ((isNumber24PossibleUtill(op1 + op2, op3)) or
(isNumber24PossibleUtill(op1 - op2, op3)) or
(isNumber24PossibleUtill(op1 * op2, op3)) or
(op2 and isNumber24PossibleUtill(op1 / op2, op3))):
return True
if (isNumber24PossibleUtill(op1, op2 + op3) or
isNumber24PossibleUtill(op1, op2 - op3) or
isNumber24PossibleUtill(op1, op2 * op3) or
op3 and isNumber24PossibleUtill(op1, op2 / op3)):
return True
return False
# Function takes given array as arr parameter
# and apply all possible operation in every
# consecutive elements and check if the remaining
# 3 parameters can be used for obtaining 24 or not
def isNumber24Possible(arr):
# Apply every operation between first two operands
if (isNumber24PossibleUtil(arr[0] + arr[1],
arr[2], arr[3]) or
isNumber24PossibleUtil(arr[0] - arr[1],
arr[2], arr[3]) or
isNumber24PossibleUtil(arr[0] * arr[1],
arr[2], arr[3]) or
arr[1] and
isNumber24PossibleUtil(arr[0] / arr[1],
arr[2], arr[3])):
return True
# Between second and third operands
if (isNumber24PossibleUtil(arr[0], arr[1] + arr[2], arr[3]) or
isNumber24PossibleUtil(arr[0], arr[1] - arr[2], arr[3]) or
isNumber24PossibleUtil(arr[0], arr[1] * arr[2], arr[3]) or
arr[2] and isNumber24PossibleUtil(arr[0], arr[1] / arr[2],
arr[3])):
return True
# Between third and fourth operands
if (isNumber24PossibleUtil(arr[0], arr[1], arr[2] + arr[3]) or
isNumber24PossibleUtil(arr[0], arr[1], arr[2] - arr[3]) or
isNumber24PossibleUtil(arr[0], arr[1], arr[2] * arr[3]) or
arr[3] and isNumber24PossibleUtil(arr[0], arr[1],
arr[2] / arr[3])):
return True
return False
# Driver Code
# Given Input
arr = [ 3, 6, 8, 2 ]
# Function Call
if (isNumber24Possible(arr)):
print("Possible")
else:
print("Not Possible")
# This code is contributed by sanjoy_62
C#
using System;
public class GFG {
static double TOLERANCE = 0.001;
// This function is used to check whether
// given two number can reduce to 24 using
// any of the 4 operations
static bool isNumber24PossibleUtil(double op1,
double op2)
{
// Check if any of the operation result to 24
if (Math.Abs(op1 + op2 - 24.0) < TOLERANCE
|| Math.Abs(op1 - op2 - 24.0) < TOLERANCE
|| Math.Abs(op1 * op2 - 24.0) < TOLERANCE
|| op2 != 0
&& Math.Abs(op1 / op2 - 24.0)
< TOLERANCE)
return true;
return false;
}
// Function which applies all the possible operations
// in between all the parameters and call the function
// which check if given number can result in 24 or not
static bool isNumber24PossibleUtil(double op1,
double op2,
double op3)
{
// Applying operation between two operands reduces
// the count of operands to two
if (isNumber24PossibleUtil(op1 + op2, op3)
|| isNumber24PossibleUtil(op1 - op2, op3)
|| isNumber24PossibleUtil(op1 * op2, op3)
|| op2 != 0
&& isNumber24PossibleUtil(op1 / op2,
op3))
return true;
if (isNumber24PossibleUtil(op1, op2 + op3)
|| isNumber24PossibleUtil(op1, op2 - op3)
|| isNumber24PossibleUtil(op1, op2 * op3)
|| op3 != 0
&& isNumber24PossibleUtil(op1,
op2 / op3))
return true;
return false;
}
// Function takes given array as arr parameter
// and apply all possible operation in every
// consecutive elements and check if the remaining
// 3 parameters can be used for obtaining 24 or not
static bool isNumber24Possible(int[] arr)
{
// Apply every operation between first two operands
if (isNumber24PossibleUtil(arr[0] + arr[1], arr[2],
arr[3])
|| isNumber24PossibleUtil(arr[0] - arr[1],
arr[2], arr[3])
|| isNumber24PossibleUtil(arr[0] * arr[1],
arr[2], arr[3])
|| arr[1] != 0
&& isNumber24PossibleUtil(
arr[0] / arr[1], arr[2], arr[3]))
return true;
// Between second and third operands
if (isNumber24PossibleUtil(arr[0], arr[1] + arr[2],
arr[3])
|| isNumber24PossibleUtil(
arr[0], arr[1] - arr[2], arr[3])
|| isNumber24PossibleUtil(
arr[0], arr[1] * arr[2], arr[3])
|| arr[2] != 0
&& isNumber24PossibleUtil(
arr[0], arr[1] / arr[2], arr[3]))
return true;
// Between third and fourth operands
if (isNumber24PossibleUtil(arr[0], arr[1],
arr[2] + arr[3])
|| isNumber24PossibleUtil(arr[0], arr[1],
arr[2] - arr[3])
|| isNumber24PossibleUtil(arr[0], arr[1],
arr[2] * arr[3])
|| arr[3] != 0
&& isNumber24PossibleUtil(
arr[0], arr[1], arr[2] / arr[3]))
return true;
return false;
}
static public void Main()
{
int[] arr = { 3, 6, 8, 2 };
// Function Call
if (isNumber24Possible(arr)) {
Console.WriteLine("Possible");
}
else {
Console.WriteLine("Not Possible");
}
}
}
// This code is contributed by maddler.
Javascript
<script>
// JavaScript program to implement above approach
// Division operation might loose some
// precision consider 0.001 as tolerance.
const TOLERANCE = 0.001
// This function is used to check whether
// given two number can reduce to 24 using
// any of the 4 operations
function isNumber24PossibleUtill(op1, op2){
// Check if any of the operation result to 24
if (Math.abs(op1 + op2 - 24.0) < TOLERANCE ||
Math.abs(op1 - op2 - 24.0) < TOLERANCE ||
Math.abs(op1 * op2 - 24.0) < TOLERANCE ||
op2 && Math.abs(op1 / op2 - 24.0) < TOLERANCE)
return true
return false
}
// Function which applies all the possible operations
// in between all the parameters and call the function
// which check if given number can result in 24 or not
function isNumber24PossibleUtil(op1, op2, op3){
// Applying operation between two operands reduces
// the count of operands to two
if ((isNumber24PossibleUtill(op1 + op2, op3)) ||
(isNumber24PossibleUtill(op1 - op2, op3)) ||
(isNumber24PossibleUtill(op1 * op2, op3)) ||
(op2 && isNumber24PossibleUtill(op1 / op2, op3)))
return true
if (isNumber24PossibleUtill(op1, op2 + op3) ||
isNumber24PossibleUtill(op1, op2 - op3) ||
isNumber24PossibleUtill(op1, op2 * op3) ||
op3 && isNumber24PossibleUtill(op1, op2 / op3))
return true
return false
}
// Function takes given array as arr parameter
// and apply all possible operation in every
// consecutive elements and check if the remaining
// 3 parameters can be used for obtaining 24 or not
function isNumber24Possible(arr){
// Apply every operation between first two operands
if (isNumber24PossibleUtil(arr[0] + arr[1],
arr[2], arr[3]) ||
isNumber24PossibleUtil(arr[0] - arr[1],
arr[2], arr[3]) ||
isNumber24PossibleUtil(arr[0] * arr[1],
arr[2], arr[3]) ||
arr[1] &&
isNumber24PossibleUtil(arr[0] / arr[1],
arr[2], arr[3]))
return true
// Between second and third operands
if (isNumber24PossibleUtil(arr[0], arr[1] + arr[2], arr[3]) ||
isNumber24PossibleUtil(arr[0], arr[1] - arr[2], arr[3]) ||
isNumber24PossibleUtil(arr[0], arr[1] * arr[2], arr[3]) ||
arr[2] && isNumber24PossibleUtil(arr[0], arr[1] / arr[2],
arr[3]))
return true
// Between third and fourth operands
if (isNumber24PossibleUtil(arr[0], arr[1], arr[2] + arr[3]) ||
isNumber24PossibleUtil(arr[0], arr[1], arr[2] - arr[3]) ||
isNumber24PossibleUtil(arr[0], arr[1], arr[2] * arr[3]) ||
arr[3] && isNumber24PossibleUtil(arr[0], arr[1],
arr[2] / arr[3]))
return true
return false
}
// Driver Code
// Given Input
let arr = [ 3, 6, 8, 2 ]
// Function Call
if (isNumber24Possible(arr))
document.write("Possible","</br>")
else
document.write("Not Possible","</br>")
// This code is contributed by shinjanpatra
</script>
Producción
Possible
Complejidad temporal: O(4 2 × 4!)
Espacio auxiliar: O(1)