# Find the Largest Cube formed by Deleting minimum Digits from a number

Given a number n, the task is to find the largest perfect cube that can be formed by deleting minimum digits(possibly 0) from the number.
X is called a perfect cube if X = Y3 for some Y.

Examples:

```Input : 4125
Output : 125
Explanation
125 = 53. We can form 125 by deleting digit 4 from 4125

Input : 876
Output :8
Explanation
8 = 23. We can form 8 by deleting digits 7 and 6 from 876
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We can generate cubes of all numbers till from 1 to N1/3 (We don’t consider 0 as 0 is not considered as a perfect cube). We iterate the cubes from largest to the smallest.
Now if we look at the number n given to us, then we know that this number contains only log(n) + 1 digits, thus we can efficiently approach the problem if we treat this number n as a string hereafter.
While iterating on the perfect cubes, we check if the perfect cube is a subsequence of the number n when its represented as a string.If this is the case then the deletions required for changing the number n to the current perfect cube is:

```No of deleted digits = No of digits in number n -
Number of digits in current
perfect cube
```

Since we want the largest cube number we traverse the array of preprocessed cubes in reverse order.

## C++

 `/* C++ code to implement maximum perfect cube  ` `   ``formed after deleting  minimum digits */` `#include ` `using` `namespace` `std; ` ` `  `// Returns vector of Pre Processed perfect cubes ` `vector preProcess(``long` `long` `int` `n) ` `{ ` `    ``vector preProcessedCubes; ` `    ``for` `(``int` `i = 1; i * i * i <= n; i++) { ` `        ``long` `long` `int` `iThCube = i * i * i; ` ` `  `        ``// convert the cube to string and push into ` `        ``// preProcessedCubes vector ` `        ``string cubeString = to_string(iThCube); ` `        ``preProcessedCubes.push_back(cubeString); ` `    ``} ` `    ``return` `preProcessedCubes; ` `} ` ` `  `/* Utility function for findLargestCube().  ` `   ``Returns the Largest cube number that can be formed */` `string findLargestCubeUtil(string num,  ` `                    ``vector preProcessedCubes) ` `{ ` `    ``// reverse the preProcessed cubes so that we  ` `    ``// have the largest cube in the beginning ` `    ``// of the vector ` `    ``reverse(preProcessedCubes.begin(), preProcessedCubes.end()); ` ` `  `    ``int` `totalCubes = preProcessedCubes.size(); ` ` `  `    ``// iterate over all cubes ` `    ``for` `(``int` `i = 0; i < totalCubes; i++) { ` `        ``string currCube = preProcessedCubes[i]; ` ` `  `        ``int` `digitsInCube = currCube.length(); ` `        ``int` `index = 0; ` `        ``int` `digitsInNumber = num.length(); ` `        ``for` `(``int` `j = 0; j < digitsInNumber; j++) { ` ` `  `            ``// check if the current digit of the cube ` `            ``// matches with that of the number num ` `            ``if` `(num[j] == currCube[index])  ` `                ``index++; ` `             `  `            ``if` `(digitsInCube == index)                  ` `                ``return` `currCube;             ` `        ``} ` `    ``} ` ` `  `    ``// if control reaches here, the its  ` `    ``// not possible  to form a perfect cube ` `    ``return` `"Not Possible"``; ` `} ` ` `  `// wrapper for findLargestCubeUtil() ` `void` `findLargestCube(``long` `long` `int` `n) ` `{ ` `    ``// pre process perfect cubes ` `    ``vector preProcessedCubes = preProcess(n); ` ` `  `    ``// convert number n to string ` `    ``string num = to_string(n); ` ` `  `    ``string ans = findLargestCubeUtil(num, preProcessedCubes); ` ` `  `    ``cout << ``"Largest Cube that can be formed from "` `         ``<< n << ``" is "` `<< ans << endl; ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``long` `long` `int` `n; ` `    ``n = 4125; ` `    ``findLargestCube(n); ` ` `  `    ``n = 876; ` `    ``findLargestCube(n); ` ` `  `    ``return` `0; ` `} `

## Java

 `/* Java code to implement maximum perfect cube  ` `formed after deleting minimum digits */` `import` `java.util.*; ` `class` `GFG  ` `{ ` ` `  `    ``// Returns vector of Pre Processed perfect cubes ` `    ``static` `Vector preProcess(``int` `n)  ` `    ``{ ` `        ``Vector preProcessedCubes = ``new` `Vector<>(); ` `        ``for` `(``int` `i = ``1``; i * i * i <= n; i++) ` `        ``{ ` `            ``int` `iThCube = i * i * i; ` ` `  `            ``// convert the cube to String and push into ` `            ``// preProcessedCubes vector ` `            ``String cubeString = String.valueOf(iThCube); ` `            ``preProcessedCubes.add(cubeString); ` `        ``} ` `        ``return` `preProcessedCubes; ` `    ``} ` ` `  `    ``/* Utility function for findLargestCube().  ` `    ``Returns the Largest cube number that can be formed */` `    ``static` `String findLargestCubeUtil(String num, ` `            ``Vector preProcessedCubes)  ` `    ``{ ` `        ``// reverse the preProcessed cubes so that we  ` `        ``// have the largest cube in the beginning ` `        ``// of the vector ` `        ``Collections.reverse(preProcessedCubes); ` ` `  `        ``int` `totalCubes = preProcessedCubes.size(); ` ` `  `        ``// iterate over all cubes ` `        ``for` `(``int` `i = ``0``; i < totalCubes; i++) ` `        ``{ ` `            ``String currCube = preProcessedCubes.get(i); ` ` `  `            ``int` `digitsInCube = currCube.length(); ` `            ``int` `index = ``0``; ` `            ``int` `digitsInNumber = num.length(); ` `            ``for` `(``int` `j = ``0``; j < digitsInNumber; j++) ` `            ``{ ` ` `  `                ``// check if the current digit of the cube ` `                ``// matches with that of the number num ` `                ``if` `(num.charAt(j) == currCube.charAt(index))  ` `                ``{ ` `                    ``index++; ` `                ``} ` ` `  `                ``if` `(digitsInCube == index)  ` `                ``{ ` `                    ``return` `currCube; ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``// if control reaches here, the its  ` `        ``// not possible to form a perfect cube ` `        ``return` `"Not Possible"``; ` `    ``} ` ` `  `    ``// wrapper for findLargestCubeUtil() ` `    ``static` `void` `findLargestCube(``int` `n)  ` `    ``{ ` `        ``// pre process perfect cubes ` `        ``Vector preProcessedCubes = preProcess(n); ` ` `  `        ``// convert number n to String ` `        ``String num = String.valueOf(n); ` ` `  `        ``String ans = findLargestCubeUtil(num, preProcessedCubes); ` ` `  `        ``System.out.println(``"Largest Cube that can be formed from "` `                ``+ n + ``" is "` `+ ans); ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``int` `n; ` `        ``n = ``4125``; ` `        ``findLargestCube(n); ` ` `  `        ``n = ``876``; ` `        ``findLargestCube(n); ` `    ``} ` `} ` ` `  `// This code has been contributed by 29AjayKumar `

/div>

## Python3

 `# Python3 code to implement maximum perfect ` `# cube formed after deleting minimum digits  ` `import` `math as mt ` ` `  `# Returns vector of Pre Processed ` `# perfect cubes ` `def` `preProcess(n): ` ` `  `    ``preProcessedCubes ``=` `list``() ` `    ``for` `i ``in` `range``(``1``, mt.ceil(n``*``*``(``1.` `/` `3.``))): ` `        ``iThCube ``=` `i``*``*``3` `         `  `        ``# convert the cube to string and  ` `        ``# push into preProcessedCubes vector ` `        ``cubeString ``=` `str``(iThCube) ` `        ``preProcessedCubes.append(cubeString) ` `         `  `    ``return` `preProcessedCubes ` ` `  `# Utility function for findLargestCube().  ` `# Returns the Largest cube number that ` `# can be formed  ` `def` `findLargestCubeUtil(num,preProcessedCubes): ` `     `  `    ``# reverse the preProcessed cubes so  ` `    ``# that we have the largest cube in  ` `    ``# the beginning of the vector ` `    ``preProcessedCubes ``=` `preProcessedCubes[::``-``1``] ` ` `  `    ``totalCubes ``=` `len``(preProcessedCubes) ` ` `  `    ``# iterate over all cubes ` `    ``for` `i ``in` `range``(totalCubes): ` `        ``currCube ``=` `preProcessedCubes[i] ` ` `  `        ``digitsInCube ``=` `len``(currCube) ` `        ``index ``=` `0` `        ``digitsInNumber ``=` `len``(num) ` `        ``for` `j ``in` `range``(digitsInNumber): ` `             `  `            ``# check if the current digit of the cube ` `            ``# matches with that of the number num ` `            ``if` `(num[j] ``=``=` `currCube[index]):  ` `                ``index ``+``=` `1` `             `  `            ``if` `(digitsInCube ``=``=` `index):              ` `                ``return` `currCube          ` `     `  `    ``# if control reaches here, the its  ` `    ``# not possible to form a perfect cube ` `    ``return` `"Not Possible"` ` `  `# wrapper for findLargestCubeUtil() ` `def` `findLargestCube(n): ` ` `  `    ``# pre process perfect cubes ` `    ``preProcessedCubes ``=` `preProcess(n) ` ` `  `    ``num ``=` `str``(n) ` ` `  `    ``ans ``=` `findLargestCubeUtil(num, preProcessedCubes) ` ` `  `    ``print``(``"Largest Cube that can be formed from"``,  ` `                                    ``n, ``"is"``, ans) ` ` `  `# Driver Code ` `n ``=` `4125` `findLargestCube(n) ` ` `  `n ``=` `876` `findLargestCube(n) ` `     `  `# This code is contributed  ` `# by mohit kumar 29 `

## C#

 `/* C# code to implement maximum perfect cube  ` `formed after deleting minimum digits */` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG  ` `{  ` ` `  `    ``// Returns vector of Pre Processed perfect cubes  ` `    ``static` `List preProcess(``int` `n)  ` `    ``{  ` `        ``List preProcessedCubes = ``new` `List();  ` `        ``for` `(``int` `i = 1; i * i * i <= n; i++)  ` `        ``{  ` `            ``int` `iThCube = i * i * i;  ` ` `  `            ``// convert the cube to String and push into  ` `            ``// preProcessedCubes vector  ` `            ``String cubeString = String.Join(``""``,iThCube);  ` `            ``preProcessedCubes.Add(cubeString);  ` `        ``}  ` `        ``return` `preProcessedCubes;  ` `    ``}  ` ` `  `    ``/* Utility function for findLargestCube().  ` `    ``Returns the Largest cube number that can be formed */` `    ``static` `String findLargestCubeUtil(String num,  ` `            ``List preProcessedCubes)  ` `    ``{  ` `        ``// reverse the preProcessed cubes so that we  ` `        ``// have the largest cube in the beginning  ` `        ``// of the vector  ` `        ``preProcessedCubes.Reverse();  ` ` `  `        ``int` `totalCubes = preProcessedCubes.Count;  ` ` `  `        ``// iterate over all cubes  ` `        ``for` `(``int` `i = 0; i < totalCubes; i++)  ` `        ``{  ` `            ``String currCube = preProcessedCubes[i];  ` ` `  `            ``int` `digitsInCube = currCube.Length;  ` `            ``int` `index = 0;  ` `            ``int` `digitsInNumber = num.Length;  ` `            ``for` `(``int` `j = 0; j < digitsInNumber; j++)  ` `            ``{  ` ` `  `                ``// check if the current digit of the cube  ` `                ``// matches with that of the number num  ` `                ``if` `(num[j] == currCube[index])  ` `                ``{  ` `                    ``index++;  ` `                ``}  ` ` `  `                ``if` `(digitsInCube == index)  ` `                ``{  ` `                    ``return` `currCube;  ` `                ``}  ` `            ``}  ` `        ``}  ` ` `  `        ``// if control reaches here, the its  ` `        ``// not possible to form a perfect cube  ` `        ``return` `"Not Possible"``;  ` `    ``}  ` ` `  `    ``// wrapper for findLargestCubeUtil()  ` `    ``static` `void` `findLargestCube(``int` `n)  ` `    ``{  ` `        ``// pre process perfect cubes  ` `        ``List preProcessedCubes = preProcess(n);  ` ` `  `        ``// convert number n to String  ` `        ``String num = String.Join(``""``,n);  ` ` `  `        ``String ans = findLargestCubeUtil(num, preProcessedCubes);  ` ` `  `        ``Console.WriteLine(``"Largest Cube that can be formed from "` `                ``+ n + ``" is "` `+ ans);  ` `    ``}  ` ` `  `    ``// Driver Code  ` `    ``public` `static` `void` `Main(String[] args)  ` `    ``{  ` `        ``int` `n;  ` `        ``n = 4125;  ` `        ``findLargestCube(n);  ` ` `  `        ``n = 876;  ` `        ``findLargestCube(n);  ` `    ``}  ` `}  ` ` `  `// This code contributed by Rajput-Ji `

## PHP

 ` `

Output:

```Largest Cube that can be formed from 4125 is 125
Largest Cube that can be formed from 876 is 8
```

Time Complexity of the above algorithm is O(N1/3log(N) log(N) is due to the fact that the number of digits in N are Log(N) + 1.