Find the Largest Cube formed by deleting minimum number of digits from a number

Reading time: 20 minutes | Coding time: 5 minutes

Given a number N, our task is to find the largest perfect cube that can be formed by deleting minimum digits (possibly 0) from the number. Any digit can be removed from the given number to reach the goal.

X is called a perfect cube if X = Y^3 for some integer Y.

If the number cannot be perfect cube print -1.

Explanation

let N = 1205;

if we remove 0 from the above number we will get 125 as remaning number, which is cube root of 5(5 * 5 * 5 = 125).

let N = 876
if we remove 7 and 6 then we will have 8 which is cube root of 2 (2 * 2 * 2 = 8)

Algorithm

We explored two approaches:

• A brute force approach O(2^N)
• A greedy approach O(N^(1/3)log(N)log(N))

Naive Solution O(2^N)

Check for every subsequence of the number check the number is cube or not and then compare it with the maximum cube among them.

To generate all substring we remove last character so that next permutation can be generated.

We have a number num = "123"

we add each element to curr string which will give us:

1
12
123

after this the recuression will return back with "12", then '2' is removed and the next iteration will be called which will give subsequence "13". This will complete the resuresion for '1', the subsequence will start from '2' which will give "2" and "23" after that "3".

This will give all the subsequence of the given number 123

1
12
123
13
2
23
3

CODE

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll mx = INT_MIN;
bool is_Cube(ll x)
{
	int found = 0;
	for (int i = 2; i <= (x / 2); i++)
	{
		if (x % i == 0)
		{
			if ((i * i * i) == x)
				found = 1;
		}
	}
	if (found == 1)
		return true;
	else
		return false;
}
void printSubSeqRec(string str, int n, int index = -1, string curr = "")
{
	if (index == n)
		return;
	if (curr != "")
	{
		ll temp = stoi(curr);
		if (is_Cube(temp))
			mx = max(mx, temp);
	}

	for (int i = index + 1; i < n; i++)
	{
		curr += str[i];
		printSubSeqRec(str, n, i, curr);
		curr = curr.erase(curr.size() - 1);
	}
	return;
}

int main()
{
    int nums = 102050; 
	string str = to_string(nums);

	printSubSeqRec(str, str.size());
	if (mx != INT_MIN)
		cout << mx;
	else
		cout << "NOT FOUND ANY CUBE";
	return 0;
}

OUTPUT

1000

The Time complexity of the above code is more than 2^n, where n is the number of digit the given number.

Greedy Algorithm O(N^(1/3)log(N)log(N))

Now, we know that the largest cube will be smaller the number its self, so we can generate perfect cubes of all numbers from 1 to N, and keep them in an array, after that starting from the largest cube we check if the cube is a subsequence of the given number if yes then we got the desired number otherwise no such number exists.

Explanation

Given Number is N = 102050

we generate all the perfect cube from 1 to N.
perfectCubes={1,8,27,64,125,216,343,512,729,1000,1331,1728,2197,2744,
3375,4096,4913,5832,6859,8000,9261,10648,12167,13824,15625,17576,19683,
21952,24389,27000,29791,32768,35937,39304,42875,46656,50653,54872,59319,
64000,68921,74088,79507,85184,91125,97336}

Now we check from the largest number weather its a subsequence of the given N number.

like here 1000 is the subsequence of 102050, so 1000 is the Largest Cube formed by Deleting minimum Digits from a number.

To check if a number is a subsequence of the given number, we iterate over the number and check if the each digit is present in the the number or not.
Eg: we have a number nums = 1025, and we have a perfect cube pc = 125, we iterate over the nums, check if nums[0] is equal to pc[index], then we move to check nums[1] is equal to pc[1], then nums[2] with pc[1], next nums[3] with pc[2], if we reach the end of the pc then pc is a subsequence of the nums, other wise not.

Code

#include <bits/stdc++.h> 
using namespace std; 

// Returns vector of Pre Processed perfect cubes 
vector<string> calPerfectCube(long long int n) 
{ 
	vector<string> perfectCubes; 
	for (int i = 1; i * i * i <= n; i++) { 
		long long int iThCube = i * i * i; 

		// convert the cube to string and push into 
		// perfectCubes vector 
		string cubeString = to_string(iThCube); 
		perfectCubes.push_back(cubeString); 
	} 
	
	return perfectCubes; 
} 

//Returns the Largest cube number that can be formed
string CheckSubSequence(string num, vector<string> perfectCubes) 
{ 
	// reverse the calPerfectCubeed cubes so that we 
	// have the largest cube in the beginning 
	// of the vector 
	reverse(perfectCubes.begin(), perfectCubes.end()); 

	int totalCubes = perfectCubes.size(); 

	// iterate over all cubes 
	for (int i = 0; i < totalCubes; i++) { 
		string currCube = perfectCubes[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"; 
} 

void FLC(long long int n) 
{ 
	// pre process perfect cubes 
	vector<string> perfectCubes = calPerfectCube(n); 

	// convert number n to string 
	string num = to_string(n); 

	string ans = CheckSubSequence(num, perfectCubes); 

	cout << "Largest Cube is " << ans << endl; 
} 

// Driver Code 
int main() 
{ 
	long long int n; 
	n = 105200; 
	FLC(n); 
	return 0; 
} 

Output

Largest Cube is 1000

Complexity

• Worst case time complexity:O(N^(1/3)log(N)log(N)
• Space complexity: O(N^(1/3))