Tìm Khối lập phương lớn nhất được hình thành bằng cách Xóa các chữ số tối thiểu khỏi một số trong C ++

Khái niệm

Đối với số N đã cho, nhiệm vụ của chúng ta là xác định khối lập phương hoàn hảo lớn nhất có thể được tạo thành bằng cách xóa các chữ số nhỏ nhất (có thể là 0) khỏi số đó. Vì vậy, bất kỳ chữ số nào cũng có thể bị xóa khỏi số đã cho để đạt được mục tiêu.

A được gọi là một khối hoàn hảo nếu A =B ^ 3 với một số nguyên B.

Người ta đã thấy rằng Nếu số không thể là in hình khối hoàn hảo -1.

Ví dụ

Cho N =1025. Người ta thấy rằng nếu chúng ta xóa số 0 khỏi số trên, chúng ta sẽ nhận được 125 là số còn lại, là căn bậc hai của 5 (5 * 5 * 5 =125).

Cho N =806. Ta thấy nếu loại bỏ 0 và 6 thì ta sẽ có 8 là số còn lại là căn bậc hai của 2 (2 * 2 * 2 =8)

Phương pháp

Chúng ta phải kiểm tra mọi dãy con của số, kiểm tra xem số đó có phải là khối lập phương hay không và sau đó so sánh nó với khối lớn nhất trong số chúng. Để tạo tất cả các chuỗi con, chúng tôi xóa ký tự cuối cùng để có thể tạo hoán vị tiếp theo.

Vì vậy, chúng tôi có một số num ="876", sau đó chúng tôi thêm từng phần tử vào chuỗi hiện tại sẽ cung cấp cho chúng tôi -

8
87
876

sau đó, đệ quy sẽ quay trở lại với "87", sau đó "7" bị loại bỏ và lần lặp tiếp theo sẽ được gọi mà sẽ cho dãy con "86". Vì vậy, điều này sẽ hoàn thành đệ quy cho '8', dãy con sẽ bắt đầu từ '7' sẽ cho "7" và "76" sau đó là "6".

Kết quả của điều này, điều này sẽ cho tất cả các dãy con của số đã cho 876.

Ví dụ

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

Đầu ra

125