แนวคิด
ในส่วนที่เกี่ยวกับตัวเลข N หน้าที่ของเราคือกำหนดลูกบาศก์ที่สมบูรณ์แบบที่ใหญ่ที่สุดที่สามารถเกิดขึ้นได้โดยการลบตัวเลขขั้นต่ำ (อาจเป็น 0) ออกจากตัวเลข จึงสามารถลบตัวเลขใด ๆ ออกจากตัวเลขที่กำหนดเพื่อไปให้ถึงเป้าหมายได้
A ถูกเรียกว่าเป็นลูกบาศก์ที่สมบูรณ์แบบถ้า A =B^3 สำหรับจำนวนเต็ม B.
จะเห็นแล้วว่า ถ้าเลขไม่ครบก็พิมพ์ -1.
ตัวอย่าง
ให้ N =1,025 เห็นว่าถ้าลบ 0 ออกจากตัวเลขด้านบนจะได้ 125 เป็นตัวเลขที่เหลือ ซึ่งก็คือ รากที่สามของ 5(5 * 5 * 5 =125)
ให้ N =806 จะเห็นได้ว่าถ้าลบ 0 กับ 6 ก็จะเหลือ 8 ตัว คือ รากที่สามของ 2 (2 * 2 * 2 =8)
วิธีการ
เราต้องตรวจสอบทุกลำดับของตัวเลข ตรวจสอบว่าตัวเลขเป็นลูกบาศก์หรือไม่ จากนั้นเปรียบเทียบกับจำนวนลูกบาศก์สูงสุด ในการสร้างสตริงย่อยทั้งหมด เราจะลบอักขระตัวสุดท้ายเพื่อให้สามารถสร้างการเปลี่ยนแปลงครั้งถัดไปได้
ดังนั้นเราจึงมีตัวเลข num ="876" หลังจากนั้นเราจะเพิ่มแต่ละองค์ประกอบในสตริงปัจจุบันซึ่งจะให้ −
8 87 876
หลังจากนี้การเรียกซ้ำจะกลับมาด้วย "87" จากนั้น '7' จะถูกลบออกและการวนซ้ำครั้งต่อไปจะถูกเรียกซึ่งจะให้ส่วนต่อท้าย "86" ดังนั้นสิ่งนี้จะทำให้การเรียกซ้ำสำหรับ '8' เสร็จสมบูรณ์ ส่วนต่อท้ายจะเริ่มต้นจาก '7' ซึ่งจะให้ "7" และ "76" ตามด้วย "6"
ด้วยเหตุนี้ สิ่งนี้จะให้ผลสืบเนื่องทั้งหมดของหมายเลขที่กำหนด 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
