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

0 0 8 minutes read

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 = Y³ for some Y.
Examples:

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

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

We can generate cubes of all numbers till from 1 to N^1/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 <bits/stdc++.h>
using namespace std;
 
// Returns vector of Pre Processed perfect cubes
vector<string> preProcess(long long int n)
{
    vector<string> 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<string> 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<string> 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<String> preProcess(int n) 
    {
        Vector<String> 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<String> 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<String> 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

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<String> preProcess(int n) 
    { 
        List<String> preProcessedCubes = new List<String>(); 
        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<String> 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<String> 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

<?php
// PHP code to implement maximum perfect
// cube formed after deleting minimum digits 
 
// Returns vector of Pre Processed
// perfect cubes
function preProcess($n)
{
 
    $preProcessedCubes = array();
    for ($i = 1; $i * $i * $i < $n; $i++)
    {
        $iThCube = $i * $i * $i;
         
        // convert the cube to string and 
        // push into preProcessedCubes vector
        $cubeString = strval($iThCube);
        array_push($preProcessedCubes,$cubeString);
    }
    return $preProcessedCubes;
}
 
// Utility function for findLargestCube(). 
// Returns the Largest cube number that
// can be formed 
function findLargestCubeUtil($num,$preProcessedCubes)
{ 
    // reverse the preProcessed cubes so 
    // that we have the largest cube in 
    // the beginning of the vector
    $preProcessedCubes = array_reverse($preProcessedCubes);
 
    $totalCubes = count($preProcessedCubes);
 
    // iterate over all cubes
    for($i = 0; $i < $totalCubes; $i++)
    {
        $currCube = $preProcessedCubes[$i];
 
        $digitsInCube = strlen($currCube);
        $index = 0;
        $digitsInNumber = strlen($num);
        for ($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 += 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()
function findLargestCube($n)
{
 
    // pre process perfect cubes
    $preProcessedCubes = preProcess($n);
 
    $num = strval($n);
 
    $ans = findLargestCubeUtil($num, $preProcessedCubes);
 
    print("Largest Cube that can be formed from ".$n." is ".$ans."\n");
}
 
// Driver Code
$n = 4125;
findLargestCube($n);
 
$n = 876;
findLargestCube($n)
     
// This code is contributed by mits
?>

Javascript

<script>
/* Javascript code to implement maximum perfect cube 
formed after deleting minimum digits */
     
    // Returns vector of Pre Processed perfect cubes
    function preProcess(n)
    {
        let preProcessedCubes =[];
        for (let i = 1; i * i * i <= n; i++)
        {
            let iThCube = i * i * i;
   
            // convert the cube to String and push into
            // preProcessedCubes vector
            let cubeString = (iThCube).toString();
            preProcessedCubes.push(cubeString);
        }
        return preProcessedCubes;
    }
     
    /* Utility function for findLargestCube(). 
    Returns the Largest cube number that can be formed */
    function findLargestCubeUtil(num,preProcessedCubes)
    {
     
        // reverse the preProcessed cubes so that we 
        // have the largest cube in the beginning
        // of the vector
        (preProcessedCubes).reverse();
   
        let totalCubes = preProcessedCubes.length;
   
        // iterate over all cubes
        for (let i = 0; i < totalCubes; i++)
        {
            let currCube = preProcessedCubes[i];
   
            let digitsInCube = currCube.length;
            let index = 0;
            let digitsInNumber = num.length;
            for (let 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()
    function findLargestCube(n)
    {
     
        // pre process perfect cubes
        let preProcessedCubes = preProcess(n);
   
        // convert number n to String
        let num = (n).toString();
   
        let ans = findLargestCubeUtil(num, preProcessedCubes);
   
        document.write("Largest Cube that can be formed from "
                + n + " is " + ans+"<br>");
    }
     
    // Driver Code
    let n;
    n = 4125;
    findLargestCube(n);
 
    n = 876;
    findLargestCube(n);
 
// This code is contributed by unknown2108
</script>

Output:

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

Time Complexity: O(N^1/3log(N) log(N), due to the fact that the number of digits in N are Log(N) + 1.
Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!