Arrange given numbers in a mathematical expression using operators [+, -, *, /] and parentheses to get value 24
Given an array arr[] consisting of 4 integers each between [1-9], the task is to check whether it is possible to get the number 24 by placing the operators +, –, /, and * between the numbers or grouping them using parenthesis. If it is possible then print “Possible“, Otherwise print “Not Possible”.
Examples:
Input: arr[] = {3, 6, 8, 2}
Output: Possible
Explanation:
One possible way to get 24 is 3 × 6 + 8 – 2 = 24.Input: arr[] = {7, 2, 10, 6}
Output: Possible
Explanation:
One possible way to get 24 is (7 × 2–10) x 6 = 24.
Approach: The simplest idea to solve this problem is based on backtracking. Follow the steps below to solve the problem:
- Create a function say isNumber24Possible(arr[]) and apply all the four operations in between each consecutive element and recursively call the function say isNumber24PossibleUtil(op1, op2, op3) which performs all possible operations on 3 numbers.
- The function isNumber24PossibleUtil(op1, op2, op3) applies all the four operation in between each consecutive elements and call the overloaded function isNumber24PossibleUtil(op1, op2) which applies operation on 2 numbers.
- The function isNumber24PossibleUtil(op1, op2) is used to check whether the given two numbers can reduce to 24 using any of the 4 operations i.e +, –, /, and *. Try every operation between the numbers, if any of them result in 24 then return true otherwise return false.
Below is the implementation of the above approach:
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 operationsbool 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 notbool 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 notbool 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 Codeint 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 approachimport 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 operationsstatic 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 notstatic 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 notstatic 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 Codepublic 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 operationsdef 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 notdef 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 notdef 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 Inputarr = [ 3, 6, 8, 2 ]# Function Callif (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 operationsfunction 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 notfunction 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 notfunction 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 Inputlet arr = [ 3, 6, 8, 2 ]// Function Callif (isNumber24Possible(arr)) document.write("Possible","</br>")else document.write("Not Possible","</br>")// This code is contributed by shinjanpatra</script> |
Output
Possible
Time Complexity: O(42 × 4!)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
