Problem

Submissions

Hints & solutions

Discuss

24 Game

Hard

0/120

Average time to solve is 45m

Contributed by

3 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:-

2
4 1 8 7
1 2 1 2

Sample Output 1:-

True
False

Explanation Of Sample Input 1:-

Test case 1:- Here, we can make 24 by (8 - 4) * (7 - 1). Hence we will return true.

Test case 2:- Here, there is no way to make 24 using these cards, so ninja can’t win, hence return false.

Sample Input 2 :-

2
6 7 8 9
1 2 3 4

Sample Output 2:-

True
True

Explanation Of Sample Input 2:-

Test case 1:- Here, we can make 24 by (8 - 4) * (7 - 1). Hence we will return true.

Test case 2:- Here, there is no way to make 24 using these cards, so ninja can’t win, hence return false.

Hint 1

Try to calculate all the possible outcome and check if anyone has score equal to 24.

Approaches (1)

Approach 1

Recursion

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:-

Initialize a vector of double ‘NUMS’, to store the number on cards as type double.
Now define a function solve to find if numbers on the cards can make 24.
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.
Else for every two numbers do all the computations.
Then recursively use the result of these two numbers to find if they can make 24.
If 24 can be made then return true, else return false.

Time Complexity

O(1)

We have an upper limit of 9216 possibilities, and we are doing O(1) work for each.

Space Complexity

O(1)

We are using a constant space independent of any variable.

(100% EXP penalty)

24 Game

Console