Largest Cube by Deleting Minimum Digits

Largest Cube by Deleting Minimum Digits asks you to carve a perfect cube out of a number by deleting digits. The trick is to flip the problem around: instead of choosing which digits to delete, choose the target cube and check whether it already hides inside the number as a subsequence.

The slow way first

You could try every subset of digits to delete — but there are 2^d subsets for a d-digit number, and checking each is hopeless. Even framing it as "which deletions minimize count" tangles two goals at once: keep the result a cube and keep it large and delete few digits.

The question to ask: what does a valid answer actually look like? It is one specific perfect cube whose digits appear inside N in order. There are not many cubes below N, so we can just enumerate them.

The idea: enumerate cubes, test as a subsequence

List every perfect cube <= N. Walk them from largest to smallest. For each cube, ask one question: are its digits a subsequence of the digits of N? The first cube that passes is automatically the largest cube we can form — and matching a subsequence keeps every digit we can, which means the fewest deletions.

Because we test largest-first, the very first match is the biggest possible answer, and a subsequence keeps the maximum digits in place — so deletions are minimized for free.

Walk through it

Step through the animation. N = 2163. We start at the largest cube <= 2163, which is 1728, and walk downward. 1728, 1331, and several others fail the subsequence test. When we reach 216, its digits 2 -> 1 -> 6 all appear in order inside 2163, so we stop and return 216, having deleted only the trailing 3.

Pseudocode

s = digits of N as a string
cubes = all k*k*k that are <= N        # 1, 8, 27, ...
for cube from largest down to smallest:
    if str(cube) is a subsequence of s:
        return cube
return -1

The Python solution

def largest_cube(n):
    s = str(n)
    cubes = [k * k * k for k in range(1, n + 1) if k * k * k <= n]
    for cube in reversed(cubes):
        c = str(cube)
        it = iter(s)
        if all(ch in it for ch in c):
            return cube
    return -1

• s is N as a string so we can scan its digits in order.
• cubes lists every perfect cube up to N; reversed(cubes) walks them largest-first.
• it = iter(s) makes a one-way cursor over the digits of N.
• all(ch in it for ch in c) is the classic subsequence trick: ch in it advances the shared iterator until it finds ch, so each digit of the cube must appear after the previous one.
• The first cube that passes is the largest reachable cube, so we return it immediately.

Complexity

There are only about N^(1/3) cubes to consider, and each subsequence check is a single linear pass over the digits — so the whole thing is fast despite N itself being large.

When this pattern shows up

Practice