Given an integer n, the task is to find the minimum number of cubes whose sum equals N.
Examples:
Input: N = 496
Output: 3
43 + 63 + 63 = 496
Note that 13 + 33 + 53 + 73 = 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 kint 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 codeint main(){ int num = 15; cout << MinOfCubed(num); return 0;} |
Java
// Java implementation of the approachclass 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 approachusing 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:
8
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 kint 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 codeint main(){ int num = 15; cout << MinOfCubedDP(num); return 0;} |
Java
// Java implementation of the approachclass 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 approachimport sys# Function to return the minimum# number of cubes whose sum is kdef 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 codenum = 15;print(MinOfCubedDP(num));# This code contributed by Rajput-Ji |
C#
// C# implementation of the approachusing 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 kfunction 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:
8
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!