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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

24 Game

Number: 679

Difficulty: Hard

Paid? No

Companies: Google, Huawei

Problem Description

Given four cards with numbers in the range [1, 9], determine whether it is possible to use the numbers, along with the operations +, -, *, / (using real division) and any number of parentheses, to form an expression that evaluates exactly to 24. Note that each operation is strictly binary (i.e., no unary negation) and you cannot concatenate digits to form larger numbers.

Key Insights

  • Consider every permutation of the four cards.
  • Use recursion/backtracking to combine numbers using all possible binary operations.
  • Check both orders for non-commutative operations (subtraction and division).
  • Handle floating point arithmetic with a tolerance threshold to account for precision issues.
  • Ensure divisions are safe by checking the divisor is not close to zero.

Space and Time Complexity

Time Complexity: Exponential in the number of cards (with only 4 cards, this is acceptable); essentially O(4!) * O(operations) per recursive call.
Space Complexity: O(n) due to recursion stack, where n is the number of cards.

Solution

This problem is solved using a recursive backtracking approach. At every recursion level, we select two numbers from the current list and apply all possible operations between them. We replace these two numbers with the result and then recursively address the reduced problem. When only one number remains, we check whether it is approximately equal to 24 within a small tolerance to handle floating point precision. Key considerations include avoiding division by zero and processing both orders of operations for non-commutative operators.

Code Solutions

def judgePoint24(cards):
    EPSILON = 1e-6  # tolerance for comparison
    
    def backtrack(numbers):
        if len(numbers) == 1:
            return abs(numbers[0] - 24) < EPSILON
        
        # try every pair of numbers
        for i in range(len(numbers)):
            for j in range(len(numbers)):
                if i != j:
                    remaining = [numbers[k] for k in range(len(numbers)) if k != i and k != j]
                    a, b = numbers[i], numbers[j]
                    
                    # list all possible outcomes for the pair (a, b)
                    candidates = [a + b, a - b, b - a, a * b]
                    if abs(b) > EPSILON:
                        candidates.append(a / b)
                    if abs(a) > EPSILON:
                        candidates.append(b / a)
                    
                    for candidate in candidates:
                        if backtrack(remaining + [candidate]):
                            return True
        return False

    return backtrack(list(map(float, cards)))

# Example usage:
cards = [4, 1, 8, 7]
print(judgePoint24(cards))  # Expected output: True
← Back to All Questions