C++で数字から最小限の桁を削除して作れる最大の立方数を見つける方法

概要

整数 N が与えられたとき、その桁をできるだけ少なく（0桁でも可）削除して得られる「最大の立方数」を求めるのが本記事のテーマです。与えられた数値からは、どの桁でも自由に削除できます。

ここでいう立方数とは、ある整数 B に対して A = B³ と表せる数のことです。たとえば 8 = 2³ や 125 = 5³ などが該当します。

なお、どのように桁を削除しても立方数を作れない場合は -1 を出力します。

具体例

例1： N = 1025 の場合、「0」を削除すると残りは 125 となり、5 × 5 × 5 = 125 なので立方数です。

例2： N = 806 の場合、「0」と「6」を削除すると残りは 8 となり、2 × 2 × 2 = 8 なので立方数です。

解法のアプローチ

この問題は、与えられた数値のすべての部分列を列挙し、それぞれが立方数かどうかを判定したうえで、その中の最大値を比較することで解けます。すべての部分列を生成するには、再帰を利用して現在の文字列に末尾の文字を追加・削除しながら組み合わせを作っていきます。

たとえば num = "876" の場合、現在の文字列に各要素を順に追加していくと、次のような部分列が生成されます。

8
87
876

その後、再帰が "87" の状態まで戻り、末尾の '7' を取り除いて次の反復に進むことで、部分列 "86" が得られます。こうして '8' から始まる再帰が完了すると、今度は '7' から始まる部分列 "7"、"76"、続いて "6" が順に生成されます。

この処理により、元の数値 876 のすべての部分列が網羅的に列挙されます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll mx1 = INT_MIN;
bool is_Cube(ll x1){
    int found = 0;
    for (int i = 2; i <= (x1 / 2); i++){
       if (x1 % i == 0){
          if ((i * i * i) == x1)
             found = 1;
       }
   }
   if (found == 1)
      return true;
   else
      return false;
}
void printSubSeqRec(string str, int n1, int index = -1, string curr1 = ""){
   if (index == n1)
      return;
   if (curr1 != ""){
      ll temp = stoi(curr1);
      if (is_Cube(temp))
         mx1 = max(mx1, temp);
   }
   for (int i = index + 1; i < n1; i++){
      curr1 += str[i];
      printSubSeqRec(str, n1, i, curr1);
      curr1 = curr1.erase(curr1.size() - 1);
   }
return;
}
int main(){
   int nums1 = 1025;
   string str1 = to_string(nums1);
   printSubSeqRec(str1, str1.size());
   if (mx1 != INT_MIN)
      cout << mx1;
   else
      cout << "NOT FOUND ANY CUBE";
   return 0;
}

出力

125

計算量と補足

n 桁の数値の場合、部分列の総数は最大 2ⁿ 個になるため、計算量は O(2ⁿ × n) 程度となります。そのため、桁数が多い入力には不向きですが、桁数が少ない範囲では十分に実用的です。

また、立方数の判定は約数を総当たりする代わりに cbrt() 関数で立方根を求め、その3乗が元の数と一致するかを確認する方法でも実装できます。こちらの方がより効率的に判定できます。