Pythonで桁を削除して作れる最大の立方数（完全立方数）を求めるアルゴリズム

ある数 N が与えられたとき、その数からできるだけ少ない桁（0桁でも可）を削除して作ることができる、最大の立方数（完全立方数）を求める問題を考えます。与えられた数からは、任意の桁を自由に削除できます。ここで、ある整数 M に対して N = M³ と表せる場合、N を立方数と呼びます。

例えば、入力が 806 の場合、出力は 8 になります。「0」と「6」を削除すれば「8」が残り、8 は 2 の 3 乗（2³ = 8）という立方数だからです。

解法のアプローチ

この問題は、次の手順で解くことができます。

1. preProcess() 関数を定義する：引数として n を受け取ります。
2. 空のリスト temp_cubes を用意します。
3. i を 1 から n の立方根の切り上げまで繰り返します。
   • cube = i³ を計算します。
   • cubeString に cube を文字列化したものを代入します。
   • cubeString を temp_cubes の末尾に追加します。
4. temp_cubes を返します。
5. solve() 関数を定義する：引数として num と temp_cubes を受け取ります。
6. temp_cubes を逆順に並べ替えます（大きい立方数から順にチェックするため）。
7. totalCubes に temp_cubes の要素数を代入します。
8. i を 0 から totalCubes まで繰り返します。
   • temp に temp_cubes[i] を代入します。
   • digitsInCube に temp の文字数を代入します。
   • index を 0 で初期化し、digitsInNumber に num の文字数を代入します。
   • j を 0 から digitsInNumber まで繰り返します。
     • num[j] が temp[index] と一致したら、index を 1 増やします。
     • digitsInCube が index と等しくなったら、temp を返します（立方数の全桁が元の数に順番通り含まれていることを意味します）。
9. どの立方数も見つからなければ「Not Possible」を返します。
10. メイン処理では以下を実行します。
    • temp_cubes = preProcess(n)
    • num = n を文字列化したもの
    • ans = solve(num, temp_cubes) を計算し、ans を返します。

実装例

理解を深めるために、以下の実装例を見てみましょう。

import math

def preProcess(n):
    temp_cubes = list()
    for i in range(1, math.ceil(n ** (1. / 3.))):
        cube = i ** 3
        cubeString = str(cube)
        temp_cubes.append(cubeString)
    return temp_cubes

def solve(num, temp_cubes):
    temp_cubes = temp_cubes[::-1]
    totalCubes = len(temp_cubes)
    for i in range(totalCubes):
        temp = temp_cubes[i]
        digitsInCube = len(temp)
        index = 0
        digitsInNumber = len(num)
        for j in range(digitsInNumber):
            if num[j] == temp[index]:
                index += 1
            if digitsInCube == index:
                return temp
    return "Not Possible"

def getLargestCube(n):
    temp_cubes = preProcess(n)
    num = str(n)
    ans = solve(num, temp_cubes)
    return ans

n = 806
print(getLargestCube(n))

入力

806

出力

8

アルゴリズムのポイント

このアルゴリズムの核心は部分列判定にあります。solve() 関数では、各立方数の文字列が、元の数の文字列の部分列（順序を保ったまま一部の文字を抜き出したもの）になっているかを二重ループで確認しています。立方数を降順に走査することで、「削除する桁数が最小」かつ「値が最大」の立方数を最初に見つけた時点で即座に結果を返せるのが特徴です。候補となる立方数は n の立方根までしか存在しないため、事前に生成しておく preProcess() との2段階構成により、効率的に探索できます。