หาเลขยกกำลังสามมากที่สุดจากการลบหลักของตัวเลขใน C++

แนวคิด

กำหนดตัวเลข N ต้องการหาเลขยกกำลังสาม (Perfect Cube) ที่ใหญ่ที่สุดที่สามารถสร้างได้จากการลบหลักตัวเลขออก (อาจลบ 0 หลัก) จากตัวเลขเดิม

Perfect Cube คือ A = B³ สำหรับจำนวนเต็ม B

ตัวอย่าง: - N = 1025 → ลบ 0 ได้ 125 = 5³ - N = 806 → ลบ 0,6 ได้ 8 = 2³ - ถ้าไม่มี → -1

วิธีการแก้ปัญหา

สร้างทุก subsequence (ย่อยลำดับ) ของตัวเลขโดยการ recursion: เพิ่มตัวเลขทีละหลัก แล้วตรวจสอบว่าเป็น perfect cube หรือไม่ เก็บค่าสูงสุด การสร้าง subsequence ทำโดยการเพิ่มตัวอักษรทีละตัว แล้ว backtrack ลบตัวสุดท้ายออก

ตัวอย่างโค้ด 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