Ninja and the game

Posted: 20 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

Ninja is feeling lonely, so he started playing online games. While searching for fun, he found an exciting game. In this game, Ninja has to choose four cards at random. On each card, there is a number between 1 to 9, both inclusive. For Ninja to win, he has to make the number 24 using the number on cards and the following operator *, /, +, -, (, ).

Help Ninja to find whether he will win the game or not, on the basis of his selection. If Ninja can win the game, print true otherwise, print false.

Example:-
If the cards Ninja chooses are 4, 1, 8, 7. Then Ninja can make 24 by (8 - 4) * (7 - 1). Hence Ninja can win, so you have to return true.
Note:-
The division operator ‘/’ represents actual division, not integer division. For example, 4 / (1 - ⅔ ) = 12.
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The next line of each test contains four space-separated integers denoting the cards which Ninja has.
Output Format:
For each test case, print true if Ninja can win the game; otherwise, print false.

Print the output of each test case in a separate file.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:-
1 <= T <= 3000
1 <= NUMS[i] <= 9 where 0 <= i <= 4

Time Limit: 1 sec
Approach 1

We can use the bracket(), so that simply means the order of operations doesn’t matter. We can operate any two cards in any manner. 

So will check all possibility of every 2 cards then we will use the result of these operations with the other 2 cards. When we get one number, as a result, check if it is 24+0.0000001, then return true, else return false.

 

Algorithm:-

  1. Initialize a vector of double ‘NUMS’, to store the number on cards as type double.
  2. Now define a function solve to find if numbers on the cards can make 24.
  3. If the size of the ‘NUMS’ vector is 1 and ‘NUMS[0]’ - 24 <= 0.0000001 then return true. This will be the base case for our recursion.
  4. Else for every two numbers do all the computations.
  5. Then recursively use the result of these two numbers to find if they can make 24.
  6. If 24 can be made then return true, else return false.
Try Problem