Given a positive integer N, the task is to check whether N can be represented as the difference between two positive perfect cubes or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: N = 124
Output: Yes
Explanation: Since 124 can be represented as (125 – 1) = (53 – 13). Therefore, print Yes.
Input: N = 4
Output: No
Approach 1:
Idea: Solve the given problem is to storing the perfect cubes of all numbers from 1 to X, where X is the maximum integer for which the difference between X3 and (X – 1)3 is at most N, in a Map and check if N can be represented as the difference 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 X natural numbers in sorted order.
- Traverse the map and check for the pair having a difference equal to N. If there exists any such pair, 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 the number N// can be represented as a difference// between two perfect cubes or notvoid differenceOfTwoPerfectCubes(int N){ // Stores the perfect cubes // of first X natural numbers map<int, int> cubes; for (int i = 1; (i * i * i) - ((i - 1) * (i - 1) * (i - 1)) <= N; i++) { cubes[i * i * i] = 1; } map<int, int>::iterator itr; // Traverse the map for (itr = cubes.begin(); itr != cubes.end(); itr++) { // Stores the first number int firstNumber = itr->first; // Stores the second number int secondNumber = N + itr->first; // Search the pair for the second // number to obtain difference N // from the Map if (cubes.find(secondNumber) != cubes.end()) { cout << "Yes"; return; } } // If N cannot be represented // as difference between two // positive perfect cubes cout << "No";}// Driver Codeint main(){ int N = 124; differenceOfTwoPerfectCubes(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to check if N can be represented // as difference of two perfect cubes or not public static void differenceOfTwoPerfectCubes(int N) { // Stores the perfect cubes // of first N natural numbers HashMap<Integer, Integer> cubes = new HashMap<>(); for (int i = 1; (i * i * i) - ((i - 1) * (i - 1) * (i - 1)) <= N; i++) cubes.put((i * i * i), 1); // 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 second // number to obtain difference N from the Map if (cubes.containsKey(secondNumber)) { System.out.println("Yes"); return; } } // If N cannot be represented as // difference of two positive perfect cubes System.out.println("No"); } // Driver code public static void main(String[] args) { int N = 124; // Function call to check if N // can be represented as // sum of two perfect cubes or not differenceOfTwoPerfectCubes(N); }}// This code is contributed by shailjapriya. |
Python3
# Python3 program for the above approach# Function to check if the number N# can be represented as a difference# between two perfect cubes or notdef differenceOfTwoPerfectCubes(N): # Stores the perfect cubes # of first X natural numbers cubes = {} i = 1 while ((i * i * i) - ((i - 1) * (i - 1) * (i - 1)) <= N): cubes[i * i * i] = 1 i += 1 # Traverse the map for itr in cubes.keys(): # Stores the first number firstNumber = itr # Stores the second number secondNumber = N + itr # Search the pair for the second # number to obtain difference N # from the Map if ((secondNumber) in cubes): print("Yes") return # If N cannot be represented # as difference between two # positive perfect cubes print("No")# Driver Codeif __name__ == "__main__": N = 124 differenceOfTwoPerfectCubes(N) # This code is contributed by ukasp. |
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 difference of two perfect cubes or notpublic static void differenceOfTwoPerfectCubes(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) - ((i - 1) * (i - 1) * (i - 1)) <= N; i++) cubes.Add((i * i * i), 1); // Traverse the map foreach(KeyValuePair<int, int> entry in cubes) { // Stores first number int firstNumber = entry.Key; // Stores second number int secondNumber = N + entry.Key; // Search the pair for the second // number to obtain difference N from the Map if (cubes.ContainsKey(secondNumber)) { Console.Write("Yes"); return; } } // If N cannot be represented as // difference of two positive perfect cubes Console.Write("No");}// Driver codestatic void Main(){ int N = 124; // Function call to check if N // can be represented as // sum of two perfect cubes or not differenceOfTwoPerfectCubes(N);}}// This code is contributed by abhinavjain194 |
Javascript
<script>// Javascript program for the above approach// Function to check if the number N// can be represented as a difference// between two perfect cubes or notfunction differenceOfTwoPerfectCubes(N){ // Stores the perfect cubes // of first X natural numbers var cubes = new Map(); for (var i = 1; (i * i * i) - ((i - 1) * (i - 1) * (i - 1)) <= N; i++) { cubes.set(i * i * i, 1); } var ans = false; cubes.forEach((value, key) => { // Stores the first number var firstNumber = key; // Stores the second number var secondNumber = N + key; // Search the pair for the second // number to obtain difference N // from the Map if (cubes.has(secondNumber)) { document.write( "Yes"); ans = true; return; } }); if(ans) { return; } // If N cannot be represented // as difference between two // positive perfect cubes document.write( "No");}// Driver Codevar N = 124;differenceOfTwoPerfectCubes(N);</script> |
Output
Yes
Time Complexity: O(?N*log N)
Auxiliary Space: O(?N)
Approach 2:
Idea: Generating all possible combinations of two perfect cubes and checking if their difference is equal to the given number N.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;// Function to check if the number N// can be represented as a difference// between two perfect cubes or notbool differenceOfTwoPerfectCubes(int N){ // Stores the perfect cubes // of first X natural numbers vector<int> cubes; for (int i = 1; i <= 100; i++) { cubes.push_back(i * i * i); } // Generate all combinations of two // perfect cubes and check if their // difference is equal to N int n = cubes.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int diff = cubes[j] - cubes[i]; if (diff == N) { return true; } } } // If N cannot be represented // as difference between two // positive perfect cubes return false;}// Driver Codeint main(){ int N = 124; if (differenceOfTwoPerfectCubes(N)) { cout << "Yes"; } else { cout << "No"; } return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class Main { // Function to check if the number N // can be represented as a difference // between two perfect cubes or not static boolean differenceOfTwoPerfectCubes(int N) { // Stores the perfect cubes // of first X natural numbers List<Integer> cubes = new ArrayList<>(); for (int i = 1; i <= 100; i++) { cubes.add(i * i * i); } // Generate all combinations of two // perfect cubes and check if their // difference is equal to N int n = cubes.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int diff = cubes.get(j) - cubes.get(i); if (diff == N) { return true; } } } // If N cannot be represented // as difference between two // positive perfect cubes return false; } // Driver Code public static void main(String[] args) { int N = 124; if (differenceOfTwoPerfectCubes(N)) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
Python3
# Python program to check if the number N# can be represented as a difference# between two perfect cubes or notimport math# Function to check if the number is a perfect cubedef isPerfectCube(N): cubeRoot = int(round(N ** (1.0 / 3.0))) return cubeRoot ** 3 == N# Function to check if the number N# can be represented as a difference# between two perfect cubes or notdef differenceOfTwoPerfectCubes(N): # Stores the perfect cubes # of first X natural numbers cubes = [] for i in range(1, 101): cubes.append(i * i * i) # Generate all combinations of two # perfect cubes and check if their # difference is equal to N n = len(cubes) for i in range(n): for j in range(i + 1, n): diff = cubes[j] - cubes[i] if diff == N: return True # If N cannot be represented # as difference between two # positive perfect cubes return False# Driver Codeif __name__ == "__main__": N = 4 if differenceOfTwoPerfectCubes(N): print("Yes") else: print("No") |
C#
using System;using System.Collections.Generic;class MainClass{ // Function to check if the number N // can be represented as a difference // between two perfect cubes or not static bool DifferenceOfTwoPerfectCubes(int N) { // Stores the perfect cubes // of first X natural numbers List<int> cubes = new List<int>(); for (int i = 1; i <= 100; i++) { cubes.Add(i * i * i); } // Generate all combinations of two // perfect cubes and check if their // difference is equal to N int n = cubes.Count; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int diff = cubes[j] - cubes[i]; if (diff == N) { return true; } } } // If N cannot be represented // as difference between two // positive perfect cubes return false; } // Driver Code static void Main(string[] args) { int N = 124; if (DifferenceOfTwoPerfectCubes(N)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }} |
Javascript
// Function to check if the number N// can be represented as a difference// between two perfect cubes or notfunction differenceOfTwoPerfectCubes(N) { // Stores the perfect cubes of first X natural numbers let cubes = []; for (let i = 1; i <= 100; i++) { cubes.push(i * i * i); } // Generate all combinations of two perfect cubes and check if their // difference is equal to N let n = cubes.length; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { let diff = cubes[j] - cubes[i]; if (diff == N) { return true; } } } // If N cannot be represented as difference between two // positive perfect cubes return false;}let N = 124;if (differenceOfTwoPerfectCubes(N)) { console.log("Yes");} else { console.log("No");} |
Output:
Yes
Time Complexity: O(N^(1/3))
Auxiliary Space: O(N^(1/3))
as we are storing all the perfect cubes less than N^(1/3) in a map
Approach 3 : Hash Set
Idea : Use Hash Set to store all possible values of the difference between two perfect cubes up to a certain limit.
Next, check if the given number N is presnt int hash or not.
Implementation :
C++
#include<bits/stdc++.h>using namespace std;// Function to check if a number is a perfect cube or notbool isPerfectCube(int n){ int cube_root = round(cbrt( n)); // Calculate the cube root of n using the // cbrt() function from the <cmath> library and // round it to the nearest integer return ( cube_root * cube_root * cube_root == n); // If the cube of the rounded cube root is // equal to n, then n is a perfect cube}// Function to check if a number can be represented as the// difference between two positive perfect cubesbool checkDifference(int n){ // Create an unordered set to store the differences // between two positive perfect cubes unordered_set<int> cubes; int cube_limit = round(cbrt(n)) + 1; for (int i = 1; i <= cube_limit; i++) { for (int j = 1; j <= cube_limit; j++) { // Calculate the difference between the cubes of // i and j int cube_diff = i * i * i - j * j * j; if (cube_diff == n) { return true; } else if (cube_diff > n) { break; } else { cubes.insert(cube_diff); } } } return (cubes.count(n) > 0);}// Main functionint main(){ int n = 124; if (checkDifference(n) && !isPerfectCube(n)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0;} |
Java
import java.util.HashSet;public class PerfectCubeAndDifference { // Function to check if a number is a perfect cube or not static boolean isPerfectCube(int n) { int cube_root = (int) Math.round(Math.cbrt(n)); return (cube_root * cube_root * cube_root == n); } // Function to check if a number can be represented as the // difference between two positive perfect cubes static boolean checkDifference(int n) { HashSet<Integer> cubes = new HashSet<>(); int cube_limit = (int) Math.round(Math.cbrt(n)) + 1; for (int i = 1; i <= cube_limit; i++) { for (int j = 1; j <= cube_limit; j++) { int cube_diff = i * i * i - j * j * j; if (cube_diff == n) { return true; } else if (cube_diff > n) { break; } else { cubes.add(cube_diff); } } } return cubes.contains(n); } public static void main(String[] args) { int n = 124; if (checkDifference(n) && !isPerfectCube(n)) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
Python
# Function to check if a number is a perfect cube or notdef isPerfectCube(n): # Calculate the cube root of n and round it to the nearest integer cube_root = round(n ** (1/3)) # If the cube of the cube root is equal to n, then n is a perfect cube return cube_root ** 3 == n# Function to check if a number can be represented as the # difference between two positive perfect cubesdef checkDifference(n): cubes = set() cube_limit = round(n ** (1/3)) + 1 # Cast to an integer for i in range(1, int(cube_limit)): # Iterate up to the integer value of cube_limit for j in range(1, int(cube_limit)): # Iterate up to the integer value of cube_limit cube_diff = i ** 3 - j ** 3 # Calculate the difference between the cubes of i and j cubes.add(cube_diff) # Add cube_diff to the HashSet return n in cubes # Check if n is present in the HashSet# Main functionn = 124if checkDifference(n) and not isPerfectCube(n): print("No")else: print("Yes") |
C#
using System;using System.Collections.Generic;class GFG{ // Function to check if a number is a perfect cube or not static bool IsPerfectCube(int n) { int cubeRoot = (int)Math.Round(Math.Pow(n, 1.0 / 3.0)); // Calculate the cube root of n return (cubeRoot * cubeRoot * cubeRoot == n); // If the cube of the cube root is equal to n, then n is a perfect cube } // Function to check if a number can be represented as the difference between two positive perfect cubes static bool CheckDifference(int n) { // Create a HashSet to store the differences between two positive perfect cubes HashSet<int> cubes = new HashSet<int>(); int cubeLimit = (int)Math.Round(Math.Pow(n, 1.0 / 3.0)) + 1; for (int i = 1; i <= cubeLimit; i++) { for (int j = 1; j <= cubeLimit; j++) { // Calculate the difference between the cubes of i and j int cubeDiff = i * i * i - j * j * j; if (cubeDiff == n) { return true; } else if (cubeDiff > n) { break; } else { cubes.Add(cubeDiff); } } } return cubes.Contains(n); } // Main function static void Main(string[] args) { int n = 124; if (CheckDifference(n) && !IsPerfectCube(n)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }} |
Javascript
//Javascript code for the above approach// Function to check if a number is a perfect cube or notfunction isPerfectCube(n) { let cube_root = Math.round(Math.cbrt(n)); // Calculate the cube root of n using the // cbrt() function and // round it to the nearest integer return (cube_root * cube_root * cube_root === n); // If the cube of the rounded cube root is // equal to n, then n is a perfect cube}// Function to check if a number can be represented as the// difference between two positive perfect cubesfunction checkDifference(n) { // Create a set to store the differences // between two positive perfect cubes let cubes = new Set(); let cube_limit = Math.round(Math.cbrt(n)) + 1; for (let i = 1; i <= cube_limit; i++) { for (let j = 1; j <= cube_limit; j++) { // Calculate the difference between the cubes of // i and j let cube_diff = i * i * i - j * j * j; if (cube_diff === n) { return true; } else if (cube_diff > n) { break; } else { cubes.add(cube_diff); } } } return cubes.has(n);}// Main functionlet n = 124;if (checkDifference(n) && !isPerfectCube(n)) { console.log("Yes");} else { console.log("No");} |
Output:
Yes
Time Complexity: O(n^(2/3))
Auxiliary Space: O(n^(1/3))
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!
