Tìm lập phương lớn nhất bằng cách xóa ít chữ số nhất trong C++

Khái niệm

Cho số N, tìm lập phương hoàn hảo lớn nhất có thể tạo được bằng cách xóa ít chữ số nhất (có thể không xóa) từ N. Lập phương hoàn hảo: A = B³ với B nguyên.

Nếu không tạo được lập phương nào → in -1.

Ví dụ: N = 1025 → xóa 0 → 125 = 5³. N = 806 → xóa 0,6 → 8 = 2³.

Phương pháp

Sinh tất cả các dãy con (subsequence) của chuỗi số. Với mỗi dãy con, kiểm tra xem có phải lập phương hoàn hảo không, cập nhật giá trị lớn nhất. Sinh dãy con bằng đệ quy: tại mỗi bước thêm chữ số tiếp theo hoặc bỏ qua.

Ví dụ (C++)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll mx1 = INT_MIN;

bool is_Cube(ll x1){
    for (int i = 2; i <= (x1 / 2); i++)
        if (x1 % i == 0 && (ll)i*i*i == x1) return true;
    return false;
}

void printSubSeqRec(string str, int n1, int index = -1, string curr1 = ""){
    if (index == n1) return;
    if (!curr1.empty()){
        ll temp = stoll(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.pop_back();
    }
}

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;
}

Đầu ra

125