Find the Largest Cube by Deleting Minimum Digits in C++

Concept

With respect of given number N, our task is to determine the largest perfect cube that can be formed by deleting minimum digits (possibly 0) from the number. So any digit can be deleted from the given number to reach the target.

A is called a perfect cube if A = B^3 for some integer B.

It has been seen that If the number cannot be perfect cube print -1.

Example

Let N = 1025. It has been seen that if we delete 0 from the above number we will get 125 as remaining number, which is cube root of 5(5 * 5 * 5 = 125).

Let N = 806. It has been seen thatif we remove 0 and 6 then we will have 8 as remaining number which is cube root of 2 (2 * 2 * 2 = 8)

Method

We have to examine for every subsequence of the number check the number is cube or not and then compare it with the maximum cube among them. Forcreating all substring we delete last character so that next permutation can be created.

So we have a number num = "876", after that we add each element to current string which will give us −

8
87
876

after this the recursion will return back with "87", then '7' is removed and the next iteration will be called which will give subsequence "86". So this will complete the recursion for '8', the subsequence will start from '7' which will give "7" and "76" after that "6".

As a result of this, this will give all the subsequence of the given number 876.

Example

 Live Demo

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

Output

125