24 Game

Hard

Roku

2 views

Topics:

ArraysRecursion

You are given an integer array cards of length 4. You have four cards, each containing a number in the range [1, 9]. You should arrange the numbers on these cards in a mathematical expression using the operators ['+', '-', '*', '/'] and the parentheses '(' and ')' to get the value 24.

You are restricted with the following rules:

The division operator '/' represents real division, not integer division.
- For example, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Every operation done is between two numbers. In particular, we cannot use '-' as a unary operator.
- For example, if cards = [1, 1, 1, 1], the expression "-1 - 1 - 1 - 1" is not allowed.
You cannot concatenate numbers together
- For example, if cards = [1, 2, 1, 2], the expression "12 + 12" is not valid.

Return true if you can get such expression that evaluates to 24, and false otherwise.

Example 1:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: cards = [1,2,1,2]
Output: false

Constraints:

cards.length == 4
1 <= cards[i] <= 9

24 Game

Hard

Roku

2 views

Topics:

ArraysRecursion

You are given an integer array cards of length 4. You have four cards, each containing a number in the range [1, 9]. You should arrange the numbers on these cards in a mathematical expression using the operators ['+', '-', '*', '/'] and the parentheses '(' and ')' to get the value 24.

You are restricted with the following rules:

The division operator '/' represents real division, not integer division.
- For example, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Every operation done is between two numbers. In particular, we cannot use '-' as a unary operator.
- For example, if cards = [1, 1, 1, 1], the expression "-1 - 1 - 1 - 1" is not allowed.
You cannot concatenate numbers together
- For example, if cards = [1, 2, 1, 2], the expression "12 + 12" is not valid.

Return true if you can get such expression that evaluates to 24, and false otherwise.

Example 1:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: cards = [1,2,1,2]
Output: false

Constraints:

cards.length == 4
1 <= cards[i] <= 9

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array contain numbers other than integers, such as decimals or fractions?
What should I return if no combination of operations yields 24? Return null, an empty string, or throw an exception?
Is the order of operations I perform significant? Should I return the expression that results in 24 if there are multiple possibilities, and if so, is there a specific order I should prioritize?
Can I use parentheses to control the order of operations?
Is the input array guaranteed to always have exactly four numbers?

Brute Force Solution

Approach

The 24 Game involves using four numbers and basic arithmetic operations to reach the number 24. A brute force strategy means trying every possible combination of numbers, operations, and orders until a solution is found.

Here's how the algorithm would work step-by-step:

First, consider all possible pairings of the four numbers. Think of it as choosing two numbers at a time to work with.
For each pair, apply all four basic arithmetic operations: addition, subtraction, multiplication, and division.
Now you have a new result and two remaining numbers. Choose one of the remaining numbers and combine it with your previous result using the four operations again.
Finally, you have one last number. Combine it with your latest result, again using all four operations.
Check if any of the final results equal 24. If so, you've found a solution.
If none of the combinations result in 24, it means that there is no solution attainable using this brute force approach.

Code Implementation

def is_24_game_solvable(numbers):
    import itertools

    # Generate all permutations of the input numbers
    for number_permutation in itertools.permutations(numbers):
        first_number = number_permutation[0]
        second_number = number_permutation[1]
        third_number = number_permutation[2]
        fourth_number = number_permutation[3]

        # Iterate through all possible operations
        operations = ['+', '-', '*', '/']
        for first_operation in operations:
            for second_operation in operations:
                for third_operation in operations:

                    # Apply operations in different orders
                    try:
                        # Order 1: ((a op b) op c) op d
                        result1 = eval('((' + str(first_number) + first_operation + str(second_number) + ')' + \
                                       second_operation + str(third_number) + ')' + third_operation + str(fourth_number))
                        # Order 2: (a op b) op (c op d)
                        result2 = eval('(' + str(first_number) + first_operation + str(second_number) + ')' + \
                                       second_operation + '(' + str(third_number) + third_operation + str(fourth_number) + ')')
                        # Order 3: (a op (b op c)) op d
                        result3 = eval('(' + str(first_number) + first_operation + '(' + str(second_number) + \
                                       second_operation + str(third_number) + '))' + third_operation + str(fourth_number))
                        # Order 4: a op ((b op c) op d)
                        result4 = eval(str(first_number) + first_operation + '((' + str(second_number) + \
                                       second_operation + str(third_number) + ')' + third_operation + str(fourth_number) + ')')
                        # Order 5: a op (b op (c op d))
                        result5 = eval(str(first_number) + first_operation + '(' + str(second_number) + \
                                       second_operation + '(' + str(third_number) + third_operation + str(fourth_number) + '))')

                        if abs(result1 - 24) < 1e-6 or abs(result2 - 24) < 1e-6 or \
                           abs(result3 - 24) < 1e-6 or abs(result4 - 24) < 1e-6 or \
                           abs(result5 - 24) < 1e-6:
                            return True
                    except ZeroDivisionError:
                        # Division by zero is not a valid operation
                        continue

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The input size is fixed at four numbers. The algorithm explores all possible combinations of these four numbers, arithmetic operations, and orderings. Since the number of combinations is constant regardless of input, the time complexity remains constant. Thus, the time complexity is O(1), not dependent on any input size n.

Space Complexity

O(1) – The brute force approach, as described, primarily involves iterative calculations using a fixed number of variables to store intermediate results. We are performing operations on pairs of numbers and then combining the results, but we're not storing all the intermediate combinations in a data structure that grows with the input size. Therefore, the algorithm's auxiliary space complexity is constant, independent of the number of input numbers, N, since we only use a few variables to keep track of the current numbers being operated on and the current result.

Optimal Solution

Approach

The goal is to use basic arithmetic operations (+, -, *, /) on four given numbers to obtain 24. The clever approach breaks down the problem by systematically combining numbers and using recursion to explore possible solutions efficiently, avoiding redundant calculations. This ensures all combinations are tested while keeping the process manageable.

Here's how the algorithm would work step-by-step:

Begin with the four input numbers.
Pick any two numbers from the list.
Perform all possible arithmetic operations (+, -, *, /) between these two numbers, which gives you a new number.
Replace the two selected numbers with the result of each operation, creating a new set of three numbers, which includes the result.
Recursively repeat steps 2-4 with each of the new sets of three numbers until you are left with a single number.
If the final single number is 24 (within a very small margin of error due to floating point calculations), you have found a valid solution.
Repeat steps 2-6, exploring every possible combination of number selections and operations. If no combination yields 24, then a solution is impossible.

Code Implementation

def is_24_game_solvable(input_numbers):
    target_value = 24
    epsilon = 0.001

    def solve_recursively(current_numbers):
        # Base case: if only one number remains
        if len(current_numbers) == 1:
            return abs(current_numbers[0] - target_value) < epsilon

        # Iterate through all pairs of numbers
        for i in range(len(current_numbers)):
            for j in range(i + 1, len(current_numbers)):
                first_number = current_numbers[i]
                second_number = current_numbers[j]

                # Create a new list without the selected numbers
                remaining_numbers = [current_numbers[k] for k in range(len(current_numbers)) if k != i and k != j]

                # Perform all possible operations
                possible_results = [
                    first_number + second_number,
                    first_number - second_number,
                    second_number - first_number,
                    first_number * second_number,
                ]
                
                #Avoid division by zero.
                if second_number != 0:
                    possible_results.append(first_number / second_number)
                if first_number != 0:
                    possible_results.append(second_number / first_number)

                # Recursively call solve with the new numbers
                for result in possible_results:
                    new_numbers = remaining_numbers + [result]
                    if solve_recursively(new_numbers):
                        return True

        return False

    # Begin recursive solution process.
    return solve_recursively(input_numbers)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The input size is fixed at four numbers. The algorithm explores all possible combinations and operations on these four numbers. Since the number of combinations and operations is bounded by a constant regardless of the specific values of the input numbers, the time complexity is O(1). The recursion depth and branching factor are also limited, preventing exponential growth relative to the input size, which remains fixed at four.

Space Complexity

O(1) – The primary space usage comes from the recursion depth and temporary lists created during each recursive call. At each level of recursion, we create a new list of numbers by replacing two chosen numbers with the result of an operation. This new list contains N-1 numbers, where N is the number of numbers in the previous level's list. Since we start with 4 numbers, the recursion depth is at most 3, and the maximum size of any of these temporary lists is also bounded by a small constant. Therefore, the auxiliary space used is constant, giving a space complexity of O(1).

Edge Cases

Case	How to Handle
Input array is null or empty	Return false immediately as no calculation can be performed with no numbers.
Input array contains less than 4 numbers	Return false as the 24 game requires exactly four numbers.
Input array contains numbers that are not integers or are outside a reasonable range (e.g., very large numbers leading to overflow)	Handle invalid input by returning false or throwing an exception, and limit input number size to avoid integer overflow.
Floating point precision errors prevent reaching exactly 24	Compare the final result to 24 with a small tolerance (e.g., absolute difference less than 1e-6).
All input numbers are the same (e.g., [6, 6, 6, 6])	The algorithm should explore all permutations and combinations of operations, and potentially find a valid solution or return false if none exist.
No solution exists for the given input numbers	The algorithm should exhaust all possible combinations and operations and return false if no combination results in 24 within the allowed tolerance.
Division by zero can occur during calculation	Check for division by zero before performing the division operation and skip or handle the case appropriately to avoid errors.
Integer overflow during intermediate calculations	Use a larger data type (e.g., long) for intermediate calculations or check for potential overflow before performing the operation.