Given an integer N, the task is to check if N can be represented as the sum of two positive perfect cubes or not.
Examples:
Input: N = 28
Output: Yes
Explanation:
Since, 28 = 27 + 1 = 33 + 13.
Therefore, the required answer is YesInput: N = 34
Output: No
Approach: The idea is to store the perfect cubes of all numbers from 1 to cubic root of N in a Map and check if N can be represented as the sum of two numbers present in the Map or not. Follow the steps below to solve the problem:
- Initialize an ordered map, say cubes, to store the perfect cubes of first N natural numbers in sorted order.
- Traverse the map and check for the pair having a sum equal to N.
- If such a pair is found having sum N, then print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if N can be represented// as sum of two perfect cubes or notvoid sumOfTwoPerfectCubes(int N){ // Stores the perfect cubes // of first N natural numbers map<int, int> cubes; for (int i = 1; i * i * i <= N; i++) cubes[i * i * i] = i; // Traverse the map map<int, int>::iterator itr; for (itr = cubes.begin(); itr != cubes.end(); itr++) { // Stores first number int firstNumber = itr->first; // Stores second number int secondNumber = N - itr->first; // Search the pair for the first // number to obtain sum N from the Map if (cubes.find(secondNumber) != cubes.end()) { cout << "True"; return; } } // If N cannot be represented as // sum of two positive perfect cubes cout << "False";}// Driver Codeint main(){ int N = 28; // Function call to check if N // can be represented as // sum of two perfect cubes or not sumOfTwoPerfectCubes(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to check if N can be represented // as sum of two perfect cubes or not public static void sumOfTwoPerfectCubes(int N) { // Stores the perfect cubes // of first N natural numbers HashMap<Integer, Integer> cubes = new HashMap<>(); for (int i = 1; i * i * i <= N; i++) cubes.put((i * i * i), i); // Traverse the map Iterator<Map.Entry<Integer, Integer> > itr = cubes.entrySet().iterator(); while (itr.hasNext()) { Map.Entry<Integer, Integer> entry = itr.next(); // Stores first number int firstNumber = entry.getKey(); // Stores second number int secondNumber = N - entry.getKey(); // Search the pair for the first // number to obtain sum N from the Map if (cubes.containsKey(secondNumber)) { System.out.println("True"); return; } } // If N cannot be represented as // sum of two positive perfect cubes System.out.println("False"); } // Driver code public static void main(String[] args) { int N = 28; // Function call to check if N // can be represented as // sum of two perfect cubes or not sumOfTwoPerfectCubes(N); }}// This code is contributed by shailjapriya. |
Python3
# Python3 program for the above approach# Function to check if N can be represented# as sum of two perfect cubes or notdef sumOfTwoPerfectCubes(N) : # Stores the perfect cubes # of first N natural numbers cubes = {} i = 1 while i*i*i <= N : cubes[i*i*i] = i i += 1 # Traverse the map for itr in cubes : # Stores first number firstNumber = itr # Stores second number secondNumber = N - itr # Search the pair for the first # number to obtain sum N from the Map if secondNumber in cubes : print("True", end = "") return # If N cannot be represented as # sum of two positive perfect cubes print("False", end = "")N = 28# Function call to check if N# can be represented as# sum of two perfect cubes or notsumOfTwoPerfectCubes(N)# This code is contributed by divyeshrabadiya07. |
Javascript
<script>// Javascript program for the above approach// Function to check if N can be represented// as sum of two perfect cubes or notfunction sumOfTwoPerfectCubes(N){ // Stores the perfect cubes // of first N natural numbers var cubes = new Map(); for (var i = 1; i * i * i <= N; i++) cubes.set(i * i * i, i); var ans = false; // Traverse the map cubes.forEach((value, key) => { // Stores first number var firstNumber = key; // Stores second number var secondNumber = N - value; // Search the pair for the first // number to obtain sum N from the Map if (cubes.has(secondNumber)) { document.write( "True"); ans = true; return; } }); if(ans) { return; } // If N cannot be represented as // sum of two positive perfect cubes document.write( "False");}// Driver Codevar N = 28;// Function call to check if N// can be represented as// sum of two perfect cubes or notsumOfTwoPerfectCubes(N);</script> |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG{ // Function to check if N can be represented // as sum of two perfect cubes or not public static void sumOfTwoPerfectCubes(int N) { // Stores the perfect cubes // of first N natural numbers Dictionary<int, int> cubes = new Dictionary<int, int>(); for (int i = 1; i * i * i <= N; i++) cubes.Add((i * i * i), i); var val = cubes.Keys.ToList(); foreach(var key in val) { // Stores first number int firstNumber = cubes[1]; // Stores second number int secondNumber = N - cubes[1]; // Search the pair for the first // number to obtain sum N from the Map if (cubes.ContainsKey(secondNumber)) { Console.Write("True"); return; } } // If N cannot be represented as // sum of two positive perfect cubes Console.Write("False"); }// Driver Codestatic public void Main(){ int N = 28; // Function call to check if N // can be represented as // sum of two perfect cubes or not sumOfTwoPerfectCubes(N);}}// This code is contributed by code_hunt. |
Output
True
Time Complexity: O(N1/3 * log(N1/3))
Auxiliary Space: O(N1/3)
Approach 2: Using two Pointers
We will declare lo to 1 and hi to cube root of n(the given number), then by (lo<=hi) this condition, if current is smaller than n we will increment the lo and in another hand if it is greater then decrement the hi, where current is (lo*lo*lo + hi*hi*hi)
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if N can be represented// as sum of two perfect cubes or notbool sumOfTwoCubes(int n){ long long int lo = 1, hi = (long long int)cbrt(n); while (lo <= hi) { long long int curr = (lo * lo * lo + hi * hi * hi); if (curr == n) // if it is same return true; return true; if (curr < n) // if the curr smaller than n increment the lo lo++; else // if the curr is greater than curr decrement // the hi hi--; } return false;}// Driver Codeint main(){ int N = 28; // Function call to check if N // can be represented as // sum of two perfect cubes or not if (sumOfTwoCubes(N)) { cout << "True"; } else { cout << "False"; } return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG {// Function to check if N can be represented// as sum of two perfect cubes or notstatic boolean sumOfTwoCubes(int n){ int lo = 1, hi = (int)Math.cbrt(n); while (lo <= hi) { int curr = (lo * lo * lo + hi * hi * hi); if (curr == n) // if it is same return true; return true; if (curr < n) // if the curr smaller than n increment the lo lo++; else // if the curr is greater than curr decrement // the hi hi--; } return false;}// Driver Codepublic static void main (String[] args) { int N = 28; // Function call to check if N // can be represented as // sum of two perfect cubes or not if (sumOfTwoCubes(N)) { System.out.println("True"); } else { System.out.println("False"); }}}// This code is contributed by shivanisinghss2110 |
Python3
# Python3 program for the above approachimport math# Function to check if N can be represented# as sum of two perfect cubes or notdef sumOfTwoCubes(n): lo = 1 hi = round(math.pow(n, 1 / 3)) while (lo <= hi): curr = (lo * lo * lo + hi * hi * hi) if (curr == n): # If it is same return true; return True if (curr < n): # If the curr smaller than n increment the lo lo += 1 else: # If the curr is greater than curr decrement # the hi hi -= 1 return False# Driver CodeN = 28# Function call to check if N# can be represented as sum of # two perfect cubes or notif (sumOfTwoCubes(N)): print("True")else: print("False") # This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach// Function to check if N can be represented// as sum of two perfect cubes or notfunction sumOfTwoCubes(n){ var lo = 1, hi = (n); while (lo <= hi) { var curr = (lo * lo * lo + hi * hi * hi); if (curr == n) // if it is same return true; return true; if (curr < n) // if the curr smaller than n increment the lo lo++; else // if the curr is greater than curr decrement // the hi hi--; } return false;}// Driver Code var N = 28; // Function call to check if N // can be represented as // sum of two perfect cubes or not if (sumOfTwoCubes(N)) { document.write("True"); } else { document.write("False"); }// This code is contributed by shivanisinghss2110</script> |
C#
// C# program for the above approachusing System;class GFG {// Function to check if N can be represented// as sum of two perfect cubes or notstatic bool sumOfTwoCubes(int n){ int lo = 1, hi = (int)Math.Pow(n, (1.0 / 3.0)); while (lo <= hi) { int curr = (lo * lo * lo + hi * hi * hi); if (curr == n) // if it is same return true; return true; if (curr < n) // if the curr smaller than n increment the lo lo++; else // if the curr is greater than curr decrement // the hi hi--; } return false;}// Driver Codepublic static void Main (String[] args) { int N = 28; // Function call to check if N // can be represented as // sum of two perfect cubes or not if (sumOfTwoCubes(N)) { Console.Write("True"); } else { Console.Write("False"); }}}// This code is contributed by shivanisinghss2110 |
Output
True
Time Complexity : O(log(cbrt(n))),where n is given number
Auxiliary Space: O(1)
Approach 3: Dynamic Programming
Here’s the Dynamic Programming (DP) approach to solve the problem of finding whether a given number N can be represented as the sum of two perfect cubes or not:
We can create a DP array dp[N+1], where dp[i] is set to 1 if the number i can be represented as the sum of two perfect cubes, and 0 otherwise. We can initialize dp[0] as 1 (since 0 can be represented as the sum of two 0’s), and dp[i] as 0 for all i > 0.
Then, we can iterate over all possible pairs of perfect cubes (i^3 + j^3) such that i^3 + j^3 <= N, and mark dp[i^3 + j^3] as 1. This can be done using two nested loops:
Here is the code below:
C++
#include <bits/stdc++.h>using namespace std;// Function to check if N can be represented// as sum of two perfect cubes or notbool sumOfTwoPerfectCubes(int N){ // DP array to store whether a number can be represented as the sum of two perfect cubes vector<int> dp(N+1, 0); // Base case: 0 can be represented as the sum of two 0's dp[0] = 1; // Mark all numbers that can be represented as the sum of two perfect cubes for (int i = 1; i * i * i <= N; i++) { for (int j = 1; j * j * j <= N - i * i * i; j++) { int sum = i * i * i + j * j * j; if (sum <= N) dp[sum] = 1; } } // Return true if N can be represented as the sum of two perfect cubes, false otherwise return dp[N];}// Driver Codeint main(){ int N = 28; // Function call to check if N // can be represented as // sum of two perfect cubes or not if (sumOfTwoPerfectCubes(N)) { cout << "True"; } else { cout << "False"; } return 0;} |
Java
import java.util.*;public class Main { // Function to check if N can be represented // as sum of two perfect cubes or not public static boolean sumOfTwoPerfectCubes(int N) { // DP array to store whether a number can be // represented as the sum of two perfect cubes int[] dp = new int[N + 1]; // Base case: 0 can be represented as the sum of two // 0's dp[0] = 1; // Mark all numbers that can be represented as the // sum of two perfect cubes for (int i = 1; i * i * i <= N; i++) { for (int j = 1; j * j * j <= N - i * i * i; j++) { int sum = i * i * i + j * j * j; if (sum <= N) dp[sum] = 1; } } // Return true if N can be represented as the sum of // two perfect cubes, false otherwise return dp[N] == 1; } // Driver Code public static void main(String[] args) { int N = 28; // Function call to check if N // can be represented as // sum of two perfect cubes or not if (sumOfTwoPerfectCubes(N)) { System.out.println("True"); } else { System.out.println("False"); } }} |
Python3
# Function to check if N can be represented# as sum of two perfect cubes or notdef sumOfTwoPerfectCubes(N): # DP array to store whether a number can be represented as the sum of two perfect cubes dp = [0] * (N + 1) # Base case: 0 can be represented as the sum of two 0's dp[0] = 1 # Mark all numbers that can be represented as the sum of two perfect cubes for i in range(1, int(N ** (1/3)) + 1): for j in range(1, int((N - i**3) ** (1/3)) + 1): sum = i**3 + j**3 if sum <= N: dp[sum] = 1 # Return true if N can be represented as the sum of two perfect cubes, false otherwise return dp[N]# Driver codeN = 28# Function call to check if N# can be represented as# sum of two perfect cubes or notif sumOfTwoPerfectCubes(N): print("True")else: print("False") |
C#
using System;public class Program { // Function to check if N can be represented // as sum of two perfect cubes or not public static bool SumOfTwoPerfectCubes(int N) { // DP array to store whether a number can be // represented as the sum of two perfect cubes int[] dp = new int[N + 1]; // Base case: 0 can be represented as the sum of two // 0's dp[0] = 1; // Mark all numbers that can be represented as the // sum of two perfect cubes for (int i = 1; i * i * i <= N; i++) { for (int j = 1; j * j * j <= N - i * i * i; j++) { int sum = i * i * i + j * j * j; if (sum <= N) dp[sum] = 1; } } // Return true if N can be represented as the sum of // two perfect cubes, false otherwise return dp[N] == 1; } // Main method public static void Main() { int N = 28; // Function call to check if N // can be represented as // sum of two perfect cubes or not if (SumOfTwoPerfectCubes(N)) { Console.WriteLine("True"); } else { Console.WriteLine("False"); } }}// This code is contributed by sarojmcy2e |
Javascript
function sumOfTwoPerfectCubes(N) { // DP array to store whether a number can be represented as the sum of two perfect cubes const dp = new Array(N + 1).fill(0); // Base case: 0 can be represented as the sum of two 0's dp[0] = 1; // Mark all numbers that can be represented as the sum of two perfect cubes for (let i = 1; i <= Math.floor(Math.pow(N, 1/3)); i++) { for (let j = 1; j <= Math.floor(Math.pow(N - Math.pow(i, 3), 1/3)); j++) { const sum = Math.pow(i, 3) + Math.pow(j, 3); if (sum <= N) { dp[sum] = 1; } } } // Return true if N can be represented as the sum of two perfect cubes, false otherwise return dp[N] === 1;}// Driver codeconst N = 28;// Function call to check if N// can be represented as// sum of two perfect cubes or notif (sumOfTwoPerfectCubes(N)) { console.log("True");} else { console.log("False");} |
Output
True
Time Complexity: O(N^(2/3)), where N is the input number.
Auxiliary Space: O(N), as we are using a DP array of size N+1 to store
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!
