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 - 1is not allowed). - Numbers cannot be glued together: cards
1and2cannot form12.
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 == 41 <= cards[i] <= 9
Hints for 24 Game
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.
Hint 2
For a pair
a, bthe results area + b,a - b,b - a,a * b,a / b(ifb != 0) andb / a(ifa != 0). Stop when one number is left.Hint 3
Floating point needs an epsilon. Even safer: keep every value as an exact fraction
num / den, and checknum == 24 * denat 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
- Represent each card as the fraction
card / 1. solve(list): if one fractionn / dis left, returnn == 24 * d.- 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]needs8 / 3. - Comparing doubles with
==fails on values like24.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