컨셉
주어진 숫자 N과 관련하여 우리의 임무는 숫자에서 최소 자릿수(0 가능)를 삭제하여 형성할 수 있는 가장 큰 완전 큐브를 결정하는 것입니다. 따라서 목표에 도달하기 위해 주어진 숫자에서 임의의 숫자를 삭제할 수 있습니다.
어떤 정수 B에 대해 A =B^3이면 A를 완전 입방체라고 합니다.
숫자가 정육면체일 수 없는 경우 -1이 인쇄되는 것을 보았습니다.
예
N =1025라고 합시다. 위의 숫자에서 0을 삭제하면 나머지 숫자로 125가 나오는 것으로 나타났습니다. 이는 5(5 * 5 * 5 =125)의 세제곱근입니다.
N =806이라고 합시다. 0과 6을 제거하면 2의 세제곱근(2 * 2 * 2 =8)인 나머지 숫자가 8이 됩니다.
방법
우리는 숫자의 모든 부분 시퀀스에 대해 숫자가 큐브인지 확인하고 그 중 최대 큐브와 비교해야 합니다. 모든 하위 문자열을 생성하면 다음 순열을 생성할 수 있도록 마지막 문자를 삭제합니다.
그래서 우리는 숫자 num ="876"을 가지고 있고, 그 후에 우리는 우리에게 줄 각 요소를 현재 문자열에 추가합니다 -
8 87 876
이 후 재귀는 "87"로 다시 반환되고 '7'이 제거되고 하위 시퀀스 "86"을 제공하는 다음 반복이 호출됩니다. 따라서 이것은 '8'에 대한 재귀를 완료하고 하위 시퀀스는 '7'에서 시작하여 "6" 다음에 "7"과 "76"을 제공합니다.
결과적으로 이것은 주어진 숫자 876의 모든 부분 수열을 줄 것입니다.
예시
#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