Minimum number of cubes whose sum equals to given number N

0 0 7 minutes read

Given an integer n, the task is to find the minimum number of cubes whose sum equals N.
Examples:

Input: N = 496
Output: 3
4³ + 6³ + 6³ = 496
Note that 1³ + 3³ + 5³ + 7³ = 496 but it requires 4 cubes.
Input: N = 15
Output: 8

Naive approach: Write a recursive method that will take every perfect cube less than N say X as part of the summation and then recur for the number of cubes required for the remaining sum N – X. The time complexity of this solution is exponential.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <iostream>
using namespace std;
 
// Function to return the minimum
// number of cubes whose sum is k
int MinOfCubed(int k)
{
    // If k is less than the 2^3
    if (k < 8)
        return k;
 
    // Initialize with the maximum
    // number of cubes required
    int res = k;
    for (int i = 1; i <= k; i++) {
        if ((i * i * i) > k)
            return res;
        res = min(res, MinOfCubed(k - (i * i * i)) + 1);
    }
    return res;
}
 
// Driver code
int main()
{
    int num = 15;
    cout << MinOfCubed(num);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG {
 
    // Function to return the minimum
    // number of cubes whose sum is k
    static int MinOfCubed(int k)
    {
        // If k is less than the 2^3
        if (k < 8)
            return k;
 
        // Initialize with the maximum
        // number of cubes required
        int res = k;
        for (int i = 1; i <= k; i++) {
            if ((i * i * i) > k)
                return res;
            res = Math.min(res, MinOfCubed(k - (i * i * i)) + 1);
        }
        return res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int num = 15;
        System.out.println(MinOfCubed(num));
    }
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python3 implementation of the approach 
 
# Function to return the minimum 
# number of cubes whose sum is k 
def MinOfCubed(k):
     
    # If k is less than the 2 ^ 3 
    if (k < 8): 
        return k; 
 
    # Initialize with the maximum 
    # number of cubes required 
    res = k; 
    for i in range(1, k + 1): 
        if ((i * i * i) > k): 
            return res; 
        res = min(res, MinOfCubed(k - (i * i * i)) + 1); 
    return res; 
 
# Driver code 
num = 15; 
print(MinOfCubed(num));
 
# This code contributed by PrinciRaj1992 

C#

// C# implementation of the approach
using System;
 
class GFG {
 
    // Function to return the minimum
    // number of cubes whose sum is k
    static int MinOfCubed(int k)
    {
        // If k is less than the 2^3
        if (k < 8)
            return k;
 
        // Initialize with the maximum
        // number of cubes required
        int res = k;
        for (int i = 1; i <= k; i++) {
            if ((i * i * i) > k)
                return res;
            res = Math.Min(res, MinOfCubed(k - (i * i * i)) + 1);
        }
        return res;
    }
 
    // Driver code
    static public void Main()
    {
        int num = 15;
        Console.WriteLine(MinOfCubed(num));
    }
}
 
// This code has been contributed by ajit.

PHP

<?php
// PHP implementation of the approach 
 
// Function to return the minimum 
// number of cubes whose sum is k 
function MinOfCubed($k) 
{ 
    // If k is less than the 2^3 
    if ($k < 8) 
        return $k; 
 
    // Initialize with the maximum 
    // number of cubes required 
    $res = $k; 
    for ($i = 1; $i <= $k; $i++)
    { 
        if (($i * $i * $i) > $k) 
            return $res; 
        $res = min($res, MinOfCubed($k - ($i *$i * $i)) + 1); 
    } 
    return $res; 
} 
 
    // Driver code 
    $num = 15; 
    echo MinOfCubed($num); 
     
    // This code is contributed by Ryuga
 
?>

Javascript

<script>
    // Javascript implementation of the approach
     
    // Function to return the minimum
    // number of cubes whose sum is k
    function MinOfCubed(k)
    {
        // If k is less than the 2^3
        if (k < 8)
            return k;
   
        // Initialize with the maximum
        // number of cubes required
        let res = k;
        for (let i = 1; i <= k; i++) {
            if ((i * i * i) > k)
                return res;
            res = Math.min(res, MinOfCubed(k - (i * i * i)) + 1);
        }
        return res;
    }
     
    let num = 15;
      document.write(MinOfCubed(num));
 
</script>

Output:

Efficient approach: If we draw the complete recursion tree for the above solution, we can see that many sub-problems are solved, again and again, so we can see that this problem has the overlapping sub-problems property. This leads us to solve the problem using the Dynamic Programming paradigm.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum
// number of cubes whose sum is k
int MinOfCubedDP(int k)
{
    vector<int> DP(k+1);
    int j = 1, t = 1;
    DP[0] = 0;
    for (int i = 1; i <= k; i++) {
        DP[i] = INT_MAX;
 
        // While current perfect cube
        // is less than current element
        while (j <= i) {
 
            // If i is a perfect cube
            if (j == i)
                DP[i] = 1;
 
            // i = (i - 1) + 1^3
            else if (DP[i] > DP[i - j])
                DP[i] = DP[i - j] + 1;
 
            // Next perfect cube
            t++;
            j = t * t * t;
        }
 
        // Re-initialization for next element
        t = j = 1;
    }
    return DP[k];
}
 
// Driver code
int main()
{
    int num = 15;
    cout << MinOfCubedDP(num);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG {
 
    // Function to return the minimum
    // number of cubes whose sum is k
    static int MinOfCubedDP(int k)
    {
        int[] DP = new int[k + 1];
        int j = 1, t = 1;
        DP[0] = 0;
        for (int i = 1; i <= k; i++) {
            DP[i] = Integer.MAX_VALUE;
 
            // While current perfect cube
            // is less than current element
            while (j <= i) {
 
                // If i is a perfect cube
                if (j == i)
                    DP[i] = 1;
 
                // i = (i - 1) + 1^3
                else if (DP[i] > DP[i - j])
                    DP[i] = DP[i - j] + 1;
 
                // Next perfect cube
                t++;
                j = t * t * t;
            }
 
            // Re-initialization for next element
            t = j = 1;
        }
        return DP[k];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int num = 15;
        System.out.println(MinOfCubedDP(num));
    }
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python implementation of the approach
import sys
 
# Function to return the minimum
# number of cubes whose sum is k
def MinOfCubedDP(k):
    DP = [0] * (k + 1);
    j = 1;
    t = 1;
    DP[0] = 0;
    for i in range(1, k + 1):
        DP[i] = sys.maxsize;
 
        # While current perfect cube
        # is less than current element
        while (j <= i):
 
            # If i is a perfect cube
            if (j == i):
                DP[i] = 1;
 
            # i = (i - 1) + 1^3
            elif (DP[i] > DP[i - j]):
                DP[i] = DP[i - j] + 1;
 
            # Next perfect cube
            t += 1;
            j = t * t * t;
 
        # Re-initialization for next element
        t = j = 1;
    return DP[k];
 
 
# Driver code
num = 15;
print(MinOfCubedDP(num));
 
# This code contributed by Rajput-Ji

C#

// C# implementation of the approach
using System;
 
class GFG {
 
    // Function to return the minimum
    // number of cubes whose sum is k
    static int MinOfCubedDP(int k)
    {
        int[] DP = new int[k + 1];
        int j = 1, t = 1;
        DP[0] = 0;
        for (int i = 1; i <= k; i++) {
            DP[i] = int.MaxValue;
 
            // While current perfect cube
            // is less than current element
            while (j <= i) {
 
                // If i is a perfect cube
                if (j == i)
                    DP[i] = 1;
 
                // i = (i - 1) + 1^3
                else if (DP[i] > DP[i - j])
                    DP[i] = DP[i - j] + 1;
 
                // Next perfect cube
                t++;
                j = t * t * t;
            }
 
            // Re-initialization for next element
            t = j = 1;
        }
        return DP[k];
    }
 
    // Driver code
    public static void Main()
    {
        int num = 15;
        Console.WriteLine(MinOfCubedDP(num));
    }
}
 
/* This code contributed by Code_Mech */

PHP

<?php
// PHP implementation of the approach
 
// Function to return the minimum
// number of cubes whose sum is k
function MinOfCubedDP($k)
{
    $DP = array($k + 1);
    $j = 1; $t = 1;
    $DP[0] = 0;
    for ($i = 1; $i <= $k; $i++) 
    {
        $DP[$i] = PHP_INT_MAX;
 
        // While current perfect cube
        // is less than current element
        while ($j <= $i) 
        {
 
            // If i is a perfect cube
            if ($j == $i)
                $DP[$i] = 1;
 
            // i = (i - 1) + 1^3
            else if ($DP[$i] > $DP[$i - $j])
                $DP[$i] = $DP[$i - $j] + 1;
 
            // Next perfect cube
            $t++;
            $j = $t * $t * $t;
        }
 
        // Re-initialization for next element
        $t = $j = 1;
    }
    return $DP[$k];
}
 
// Driver code
$num = 15;
echo(MinOfCubedDP($num));
 
// This code contributed by Code_Mech 
?>

Javascript

<script>
 
    // Javascript implementation of the approach
     
    // Function to return the minimum
    // number of cubes whose sum is k
    function MinOfCubedDP(k)
    {
        let DP = new Array(k + 1);
        DP.fill(0);
        let j = 1, t = 1;
        DP[0] = 0;
        for (let i = 1; i <= k; i++) {
            DP[i] = Number.MAX_VALUE;
  
            // While current perfect cube
            // is less than current element
            while (j <= i) {
  
                // If i is a perfect cube
                if (j == i)
                    DP[i] = 1;
  
                // i = (i - 1) + 1^3
                else if (DP[i] > DP[i - j])
                    DP[i] = DP[i - j] + 1;
  
                // Next perfect cube
                t++;
                j = t * t * t;
            }
  
            // Re-initialization for next element
            t = j = 1;
        }
        return DP[k];
    }
     
    let num = 15;
    document.write(MinOfCubedDP(num));
 
</script>

Output:

At the first glance, it seems that the algorithm works in polynomial time because we have two nested loops, the outer loop takes O(n), and the inner loop takes O(n^(1/3)). So the overall algorithm takes O(n*n^(1/3)). But what is the complexity as a function of input length? To represent a number in size of n we need m=log(n) – (log of base 2) bits. In this case n=2^m. If we set 2^m as n in the formula O(n*n^(1/3)), we see that the time complexity is still exponential. This algorithm is called Pseudo-polynomial.

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!