You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through
) to get the value of 24.
Input: [4, 1, 8, 7] Output: True Explanation: (8-4) * (7-1) = 24
Input: [1, 2, 1, 2] Output: False
/represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
-as a unary operator. For example, with
[1, 1, 1, 1]as input, the expression
-1 - 1 - 1 - 1is not allowed.
[1, 2, 1, 2], we cannot write this as 12 + 12.
Intuition and Algorithm\n
There are only 4 cards and only 4 operations that can be performed. Even when all operations do not commute, that gives us an upper bound of possibilities, which makes it feasible to just try them all. Specifically, we choose two numbers (with order) in 12 ways and perform one of 4 operations (12 * 4). Then, with 3 remaining numbers, we choose 2 of them and perform one of 4 operations (6 * 4). Finally we have two numbers left and make a final choice of 2 * 4 possibilities.\n
We will perform 3 binary operations (
+, -, *, / are the operations) on either our numbers or resulting numbers. Because
/ do not commute, we must be careful to consider both
a / b and
b / a.
For every way to remove two numbers
a, b in our list, and for each possible result they can make, like
a/b, etc., we will recursively solve the problem on this smaller list of numbers.
Time Complexity: . There is a hard limit of 9216 possibilities, and we do work for each of them.\n
Space Complexity: . Our intermediate arrays are at most 4 elements, and the number made is bounded by an factor.\n
Analysis written by: @awice\n