We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

24 Game

Difficulty: Hard

Problem Description

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. Return true if you can get such an expression that evaluates to 24, and false otherwise.

Key Insights

  • You can use any combination of the four numbers with the four basic arithmetic operations.
  • You must consider all permutations of the numbers since the order of operations can affect the result.
  • Parentheses can change the order of operations, which means you need to explore different grouping of the numbers.
  • The division operator requires special attention because it needs to handle floating-point numbers and cannot divide by zero.

Space and Time Complexity

Time Complexity: O(1) - Since the number of possible operations and permutations is constant (with only 4 cards). Space Complexity: O(1) - Only a fixed amount of space is used for calculations, regardless of input size.

Solution

The solution uses a backtracking approach to explore all possible combinations of the four numbers and operations to determine if any expression evaluates to 24. It utilizes permutations to generate different orders for the numbers and recursively applies each operation while checking for the result.

Code Solutions

from itertools import permutations, product

def canGet24(cards):
    def evaluate(a, b, op):
        if op == '+': return a + b
        if op == '-': return a - b
        if op == '*': return a * b
        if op == '/': 
            return a / b if b != 0 else float('inf')  # Avoid division by zero

    def backtrack(nums):
        if len(nums) == 1:
            return abs(nums[0] - 24) < 1e-6  # Check if the final number is 24

        for i in range(len(nums)):
            for j in range(len(nums)):
                if i != j:  # Ensure we're using different numbers
                    remaining = [nums[k] for k in range(len(nums)) if k != i and k != j]
                    for op in '+-*':
                        # Calculate the new number based on the operation
                        if op == '+':
                            new_num = evaluate(nums[i], nums[j], op)
                        elif op == '-':
                            new_num = evaluate(nums[i], nums[j], op)
                        elif op == '*':
                            new_num = evaluate(nums[i], nums[j], op)
                        if backtrack(remaining + [new_num]):
                            return True

                    # Check division separately to avoid zero division
                    if nums[j] != 0:
                        new_num = evaluate(nums[i], nums[j], '/')
                        if backtrack(remaining + [new_num]):
                            return True
        return False

    for perm in permutations(cards):
        if backtrack(list(perm)):
            return True
    return False
← Back to All Questions