24 Game

Hard
1587.

24 Game

24 Game is a hard coding problem on arrays, math and backtracking, asked in Amazon, Google and Uber interviews.

You hold four cards, each showing a number from 1 to 9. Decide whether you can combine all four numbers, each used exactly once, with +, -, *, / and any parentheses, into an expression whose value is exactly 24.

Rules:

  • / is real division, not integer division: 4 / (1 - 2 / 3) = 12.
  • Every operator is binary; - cannot be used to negate a single number (-1 - 1 - 1 - 1 is not allowed).
  • Numbers cannot be glued together: cards 1 and 2 cannot form 12.

Return true if 24 can be reached.

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

Example 3

Input
cards = [3,3,8,8]
Output
true
Explanation
8 / (3 - 8 / 3) = 24 — it needs a fraction along the way.

Constraints

  • cards.length == 4
  • 1 <= cards[i] <= 9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} cards
 * @return {boolean}
 */
var judgePoint24 = function(cards) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

24 Game — Solution in Python, Java & C++

24 Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon, Google and Uber.

24 Game is a hard coding problem on arrays, math and backtracking, asked in Amazon, Google and Uber interviews.

  • Difficulty: Hard
  • Topics: Arrays, Math, Backtracking
  • Asked at: Amazon, Google, Uber
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You hold four cards, each showing a number from 1 to 9. Decide whether you can combine all four numbers, each used exactly once, with +, -, *, / and any parentheses, into an expression whose value is exactly 24.

Rules:

  • / is real division, not integer division: 4 / (1 - 2 / 3) = 12.
  • Every operator is binary; - cannot be used to negate a single number (-1 - 1 - 1 - 1 is not allowed).
  • Numbers cannot be glued together: cards 1 and 2 cannot form 12.

Return true if 24 can be reached.

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

Example 3

Input: cards = [3,3,8,8]
Output: true
Explanation: 8 / (3 - 8 / 3) = 24 — it needs a fraction along the way.

Constraints

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

Hints for 24 Game

  1. Hint 1

    Any expression combines two of the current numbers into one at some point. Pick an (unordered) pair, replace it by each possible result, and recurse on the shorter list.

  2. Hint 2

    For a pair a, b the results are a + b, a - b, b - a, a * b, a / b (if b != 0) and b / a (if a != 0). Stop when one number is left.

  3. Hint 3

    Floating point needs an epsilon. Even safer: keep every value as an exact fraction num / den, and check num == 24 * den at the end.

How to solve 24 Game

Search over the order in which numbers are merged. With exact fractions there is no rounding, so the check at the end is a plain integer comparison.

Approach

  1. Represent each card as the fraction card / 1.
  2. solve(list): if one fraction n / d is left, return n == 24 * d.
  3. Otherwise, for every pair i < j, build the list without them and append, in turn, each combination: sum, both differences, product, and both quotients whose divisor is non-zero. Recurse; succeed if any branch does.

Why it works

Every fully parenthesised expression is a binary tree, and evaluating it bottom-up merges two values at a time — so some sequence of pair merges reproduces any expression, and the search tries them all. Fractions a/b ± c/d = (ad ± bc)/bd, (a/b)(c/d) = ac/bd, (a/b)/(c/d) = ad/bc are exact, and with four cards up to 9 the numerators and denominators stay small integers.

Complexity

  • Time — O(1) — at most 6 · 6 · 3 · 6 · 1 · 6 ≈ 3,900 leaves
  • Space — O(1)

Pitfalls

  • Integer division gives wrong answers: [3,3,8,8] needs 8 / 3.
  • Comparing doubles with == fails on values like 24.000000000000004; use fractions or an epsilon.
  • Subtraction and division are not symmetric — try both orders for every pair.

Reference solution

Python

from typing import List

def judgePoint24(cards: List[int]) -> bool:
    def solve(fr):
        if len(fr) == 1:
            return fr[0][0] == 24 * fr[0][1]
        k = len(fr)
        for i in range(k):
            for j in range(i + 1, k):
                rest = [fr[t] for t in range(k) if t != i and t != j]
                a, b = fr[i]
                c, d = fr[j]
                cand = [(a * d + c * b, b * d), (a * d - c * b, b * d), (c * b - a * d, b * d), (a * c, b * d)]
                if c != 0:
                    cand.append((a * d, b * c))
                if a != 0:
                    cand.append((c * b, d * a))
                for f in cand:
                    if solve(rest + [f]):
                        return True
        return False

    return solve([(v, 1) for v in cards])

Java

public static boolean judgePoint24(int[] cards) {
    long[] nums = new long[4];
    long[] dens = new long[4];
    for (int i = 0; i < 4; i++) { nums[i] = cards[i]; dens[i] = 1; }
    return solve24(nums, dens, 4);
}

static boolean solve24(long[] nums, long[] dens, int k) {
    if (k == 1) return nums[0] == 24 * dens[0];
    for (int i = 0; i < k; i++) {
        for (int j = i + 1; j < k; j++) {
            long[] rn = new long[k - 1];
            long[] rd = new long[k - 1];
            int m = 0;
            for (int t = 0; t < k; t++) if (t != i && t != j) { rn[m] = nums[t]; rd[m] = dens[t]; m++; }
            long a = nums[i], b = dens[i], c = nums[j], d = dens[j];
            long[] cn = {a * d + c * b, a * d - c * b, c * b - a * d, a * c, a * d, c * b};
            long[] cd = {b * d, b * d, b * d, b * d, b * c, d * a};
            for (int x = 0; x < 6; x++) {
                if (x == 4 && c == 0) continue;
                if (x == 5 && a == 0) continue;
                rn[m] = cn[x];
                rd[m] = cd[x];
                if (solve24(rn, rd, k - 1)) return true;
            }
        }
    }
    return false;
}

C++

bool solve24(vector<long long> nums, vector<long long> dens) {
    int k = nums.size();
    if (k == 1) return nums[0] == 24 * dens[0];
    for (int i = 0; i < k; i++) {
        for (int j = i + 1; j < k; j++) {
            vector<long long> rn, rd;
            for (int t = 0; t < k; t++) if (t != i && t != j) { rn.push_back(nums[t]); rd.push_back(dens[t]); }
            long long a = nums[i], b = dens[i], c = nums[j], d = dens[j];
            long long cn[6] = {a * d + c * b, a * d - c * b, c * b - a * d, a * c, a * d, c * b};
            long long cd[6] = {b * d, b * d, b * d, b * d, b * c, d * a};
            for (int x = 0; x < 6; x++) {
                if (x == 4 && c == 0) continue;
                if (x == 5 && a == 0) continue;
                rn.push_back(cn[x]);
                rd.push_back(cd[x]);
                if (solve24(rn, rd)) return true;
                rn.pop_back();
                rd.pop_back();
            }
        }
    }
    return false;
}

bool judgePoint24(vector<int>& cards) {
    vector<long long> nums(cards.begin(), cards.end());
    vector<long long> dens(4, 1);
    return solve24(nums, dens);
}

JavaScript

var judgePoint24 = function(cards) {
    var solve = function(nums, dens) {
        var k = nums.length;
        if (k === 1) return nums[0] === 24 * dens[0];
        for (var i = 0; i < k; i++) {
            for (var j = i + 1; j < k; j++) {
                var rn = [], rd = [];
                for (var t = 0; t < k; t++) if (t !== i && t !== j) { rn.push(nums[t]); rd.push(dens[t]); }
                var a = nums[i], b = dens[i], c = nums[j], d = dens[j];
                var cn = [a * d + c * b, a * d - c * b, c * b - a * d, a * c];
                var cd = [b * d, b * d, b * d, b * d];
                if (c !== 0) { cn.push(a * d); cd.push(b * c); }
                if (a !== 0) { cn.push(c * b); cd.push(d * a); }
                for (var x = 0; x < cn.length; x++) {
                    rn.push(cn[x]);
                    rd.push(cd[x]);
                    if (solve(rn, rd)) return true;
                    rn.pop();
                    rd.pop();
                }
            }
        }
        return false;
    };
    return solve(cards.slice(), [1, 1, 1, 1]);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Backtracking