Perfect Cube
Given a number N, the task is to check whether the given number N is a perfect cube or not.
Examples:
Input: N = 216
Output: Yes
Explanation:
As 216 = 6*6*6. Therefore the cube root of 216 is 6.Input: N = 100
Output: No
Method 1: Naive Approach
The idea is to check for each number from 1 to N if the cube of any of these numbers equals N. If so, then that number is the cube root of N and the N is a perfect cube.
Below is the implementation of the above approach:
C++
// C++ program to check whether the given // number N is the perfect cube or not . #include <bits/stdc++.h> using namespace std; // Function to check if a number // is a perfect Cube or not void perfectCube( int N) { int cube; // Iterate from 1-N for ( int i; i <= N; i++) { // Find the cube of // every number cube = i * i * i; // Check if cube equals // N or not if (cube == N) { cout << "Yes" ; return ; } else if (cube > N) { cout << "NO" ; return ; } } } // Driver code int main() { int N = 216; // Function call perfectCube(N); return 0; } |
Java
// Java program to check whether the given // number N is the perfect cube or not class GFG { // Function to check if a number // is a perfect Cube or not static void perfectCube( int N) { int cube; // Iterate from 1-N for ( int i = 0 ; i <= N; i++) { // Find the cube of // every number cube = i * i * i; // Check if cube equals // N or not if (cube == N) { System.out.println( "Yes" ); return ; } else if (cube > N) { System.out.println( "NO" ); return ; } } } // Driver code public static void main (String[] args) { int N = 216 ; // Function call perfectCube(N); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 program to check whether the given # number N is the perfect cube or not # Function to check if a number # is a perfect Cube or not def perfectCube(N) : cube = 0 ; # Iterate from 1-N for i in range (N + 1 ) : # Find the cube of # every number cube = i * i * i; # Check if cube equals # N or not if (cube = = N) : print ( "Yes" ); return ; elif (cube > N) : print ( "NO" ); return ; # Driver code if __name__ = = "__main__" : N = 216 ; # Function call perfectCube(N); # This code is contributed by Yash_R |
C#
// C# program to check whether the given // number N is the perfect cube or not using System; class GFG { // Function to check if a number // is a perfect Cube or not static void perfectCube( int N) { int cube; // Iterate from 1-N for ( int i = 0; i <= N; i++) { // Find the cube of // every number cube = i * i * i; // Check if cube equals // N or not if (cube == N) { Console.WriteLine( "Yes" ); return ; } else if (cube > N) { Console.WriteLine( "NO" ); return ; } } } // Driver code public static void Main ( string [] args) { int N = 216; // Function call perfectCube(N); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // JavaScript program to check whether the given // number N is the perfect cube or not // Function to check if a number // is a perfect Cube or not function perfectCube(N) { let cube; // Iterate from 1-N for (let i = 0; i <= N; i++) { // Find the cube of // every number cube = i * i * i; // Check if cube equals // N or not if (cube === N) { document.write( "Yes" ); return ; } else if (cube > N) { document.write( "NO" ); return ; } } } // Driver code let N = 216; // Function call perfectCube(N); // This code is contributed by Manoj. </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Method 2: Using inbuilt function
The idea is to use the inbuilt function (cbrt()) to find the cube root of a number which returns floor value of the cube root of the number N. If the cube of this number equals N, then N is a perfect cube otherwise N is not a perfect cube.
Below is the implementation of the above approach:
C++
// C++ program to check whether the given // number N is the perfect cube or not #include <bits/stdc++.h> using namespace std; // Function to check if a number is // a perfect Cube using inbuilt function void perfectCube( int N) { int cube_root; cube_root = round(cbrt(N)); // If cube of cube_root is equals to N, // then print Yes Else print No if (cube_root * cube_root * cube_root == N) { cout << "Yes" ; return ; } else { cout << "NO" ; return ; } } // Driver's code int main() { int N = 125; // Function call to check // N is cube or not perfectCube(N); return 0; } |
Java
// Java program to check whether the given // number N is the perfect cube or not public class GFG { // Function to check if a number is // a perfect Cube using inbuilt function static void perfectCube( int N) { int cube_root; cube_root = ( int )Math.round(Math.cbrt(N)); // If cube of cube_root is equals to N, // then print Yes Else print No if (cube_root * cube_root * cube_root == N) { System.out.println( "Yes" ); return ; } else { System.out.println( "NO" ); return ; } } // Driver's code public static void main (String[] args) { int N = 125 ; // Function call to check // N is cube or not perfectCube(N); } } // This code is contributed by AnkitRai01 |
Python3
# Python program to check whether the given # number N is the perfect cube or not # Function to check if a number is # a perfect Cube using inbuilt function def perfectCube(N) : cube_root = round (N * * ( 1 / 3 )); # If cube of cube_root is equals to N, # then print Yes Else print No if cube_root * cube_root * cube_root = = N : print ( "Yes" ); return ; else : print ( "NO" ); return ; # Driver's code if __name__ = = "__main__" : N = 125 ; # Function call to check # N is cube or not perfectCube(N); # This code is contributed by AnkitRai01 |
C#
// C# program to check whether the given // number N is the perfect cube or not using System; class GFG { // Function to check if a number is // a perfect Cube using inbuilt function static void perfectCube( int N) { int cube_root; cube_root = ( int )Math.Round(Math.Cbrt(N)); // If cube of cube_root is equals to N, // then print Yes Else print No if (cube_root * cube_root * cube_root == N) { Console.WriteLine( "Yes" ); return ; } else { Console.WriteLine( "NO" ); return ; } } // Driver's code public static void Main ( string [] args) { int N = 125; // Function call to check // N is cube or not perfectCube(N); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript program to check whether the given // number N is the perfect cube or not // Function to check if a number is // a perfect Cube using inbuilt function function perfectCube(N) { let cube_root; cube_root = Math.round(Math.cbrt(N)); // If cube of cube_root is equals to N, // then print Yes Else print No if ((cube_root * cube_root * cube_root) == N) { document.write( "Yes" ); return ; } else { document.write( "NO" ); return ; } } // Driver's code let N = 125; // Function call to check // N is cube or not perfectCube(N); // This code is contributed by subhammahato348. </script> |
Yes
Time Complexity: O(logN) because using inbuilt cbrt function
Auxiliary Space: O(1)
Method 3: Using Prime Factors
- Find all the Prime Factors of the given number N using the approach in this article.
- Store the frequency of all the prime factors obtained above in a Hash Map.
- Traverse the Hash Map and if the frequency of every prime factors is not a multiple of 3, then the given number N is not a perfect cube.
Below is the implementation of the above approach:
C++
// C++ program to check if a number // is a perfect cube using prime factors #include<bits/stdc++.h> using namespace std; // Inserts the prime factor in HashMap // if not present // if present updates it's frequency map< int , int > insertPF(map< int , int > primeFact, int fact) { if (primeFact.find(fact) != primeFact.end()) { primeFact[fact]++; } else { primeFact[fact] = 1; } return primeFact; } // A utility function to find all // prime factors of a given number N map< int , int > primeFactors ( int n) { map< int , int > primeFact; // Insert the number of 2s // that divide n while (n % 2 == 0) { primeFact = insertPF(primeFact, 2); n /= 2; } // n must be odd at this point // So we can skip one element for ( int i = 3; i <= sqrt (n); i += 2) { // while i divides n, insert // i and divide n while (n % i == 0) { primeFact = insertPF(primeFact, i); n /= i; } } // This condition is to handle // the case when n is a prime // number greater than 2 if (n > 2) primeFact = insertPF(primeFact, n); return primeFact; } // Function to check if a // number is perfect cube string perfectCube ( int n) { map< int , int > primeFact; primeFact = primeFactors(n); // Iteration in Map for ( auto x : primeFact) { if (x.second % 3 != 0) return "No" ; } return "Yes" ; } // Driver Code int main() { int N = 216; // Function to check if N is // perfect cube or not cout << perfectCube(N); return 0; } // This code is contributed by himanshu77 |
Java
// Java program to check if a number // is a perfect cube using prime factors import java.io.*; import java.lang.*; import java.util.*; class GFG { // Inserts the prime factor in the Hash Map // if not present // If present updates it's frequency public static HashMap<Integer, Integer> insertPF(HashMap<Integer, Integer> primeFact, int fact) { if (primeFact.containsKey(fact)) { int freq; freq = primeFact.get(fact); primeFact.replace(fact, ++freq); } else { primeFact.put(fact, 1 ); } return primeFact; } // A utility function to find all // prime factors of a given number N public static HashMap<Integer, Integer> primeFactors( int n) { HashMap<Integer, Integer> primeFact = new HashMap<>(); // Insert the number of 2s // that divide n while (n % 2 == 0 ) { primeFact = insertPF(primeFact, 2 ); n /= 2 ; } // n must be odd at this point. // So we can skip one element for ( int i = 3 ; i <= Math.sqrt(n); i += 2 ) { // While i divides n, insert i // and divide n while (n % i == 0 ) { primeFact = insertPF(primeFact, i); n /= i; } } // This condition is to handle // the case when n is a prime // number greater than 2 if (n > 2 ) primeFact = insertPF(primeFact, n); return primeFact; } // Function to check if a number // is a perfect cube public static String perfectCube( int n) { HashMap<Integer, Integer> primeFact; primeFact = primeFactors(n); // Using values() for iteration // over keys for ( int freq : primeFact.values()) { if (freq % 3 != 0 ) return "No" ; } return "Yes" ; } // Driver Code public static void main(String[] args) { int N = 216 ; // Function to check if N is // perfect cube or not System.out.println(perfectCube(N)); } } |
Python3
# Python3 program to check if a number # is a perfect cube using prime factors import math # Inserts the prime factor in HashMap # if not present # if present updates it's frequency def insertPF(primeFact, fact) : if (fact in primeFact) : primeFact[fact] + = 1 else : primeFact[fact] = 1 return primeFact # A utility function to find all # prime factors of a given number N def primeFactors (n) : primeFact = {} # Insert the number of 2s # that divide n while (n % 2 = = 0 ) : primeFact = insertPF(primeFact, 2 ) n = n / / 2 # n must be odd at this point # So we can skip one element for i in range ( 3 , int (math.sqrt(n)) + 1 , 2 ) : # while i divides n, insert # i and divide n while (n % i = = 0 ) : primeFact = insertPF(primeFact, i) n = n / / i # This condition is to handle # the case when n is a prime # number greater than 2 if (n > 2 ) : primeFact = insertPF(primeFact, n) return primeFact # Function to check if a # number is perfect cube def perfectCube (n) : primeFact = {} primeFact = primeFactors(n) # Iteration in Map for x in primeFact : if (primeFact[x] % 3 ! = 0 ) : return "No" return "Yes" N = 216 # Function to check if N is # perfect cube or not print (perfectCube(N)) # This code is contributed by divyeshrabadiya07. |
C#
// C# program to check if a number // is a perfect cube using prime factors using System; using System.Collections.Generic; public class GFG { // Inserts the prime factor in the Hash Map // if not present // If present updates it's frequency public static Dictionary< int , int > insertPF(Dictionary< int , int > primeFact, int fact) { if (primeFact.ContainsKey(fact)) { int freq; freq = primeFact[fact]; primeFact[fact] = ++freq; } else { primeFact.Add(fact, 1); } return primeFact; } // A utility function to find all // prime factors of a given number N public static Dictionary< int , int > primeFactors( int n) { Dictionary< int , int > primeFact = new Dictionary< int , int >(); // Insert the number of 2s // that divide n while (n % 2 == 0) { primeFact = insertPF(primeFact, 2); n /= 2; } // n must be odd at this point. // So we can skip one element for ( int i = 3; i <= Math.Sqrt(n); i += 2) { // While i divides n, insert i // and divide n while (n % i == 0) { primeFact = insertPF(primeFact, i); n /= i; } } // This condition is to handle // the case when n is a prime // number greater than 2 if (n > 2) primeFact = insertPF(primeFact, n); return primeFact; } // Function to check if a number // is a perfect cube public static String perfectCube( int n) { Dictionary< int , int > primeFact; primeFact = primeFactors(n); // Using values() for iteration // over keys foreach ( int freq in primeFact.Values) { if (freq % 3 != 0) return "No" ; } return "Yes" ; } // Driver Code public static void Main(String[] args) { int N = 216; // Function to check if N is // perfect cube or not Console.WriteLine(perfectCube(N)); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // Javascript program to check if a number // is a perfect cube using prime factors // Inserts the prime factor in HashMap // if not present // if present updates it's frequency function insertPF(primeFact, fact) { if (primeFact.has(fact)) { primeFact.set(fact, primeFact.get(fact)+1); } else { primeFact.set(fact, 1); } return primeFact; } // A utility function to find all // prime factors of a given number N function primeFactors (n) { var primeFact = new Map(); // Insert the number of 2s // that divide n while (n % 2 == 0) { primeFact = insertPF(primeFact, 2); n = parseInt(n/2); } // n must be odd at this point // So we can skip one element for ( var i = 3; i <= Math.sqrt(n); i += 2) { // while i divides n, insert // i and divide n while (n % i == 0) { primeFact = insertPF(primeFact, i); n =parseInt(n/i); } } // This condition is to handle // the case when n is a prime // number greater than 2 if (n > 2) primeFact = insertPF(primeFact, n); return primeFact; } // Function to check if a // number is perfect cube function perfectCube (n) { var primeFact = new Map(); primeFact = primeFactors(n); // Iteration in Map primeFact.forEach((value, key) => { if (value % 3 != 0) return "No" ; }); return "Yes" ; } // Driver Code var N = 216; // Function to check if N is // perfect cube or not document.write( perfectCube(N)); // This code is contributed by rrrtnx. </script> |
Yes
Time Complexity: O(sqrt(n))
Auxiliary Space: O(sqrt(n))
Method 4 : Using Binary Search
The idea is to use the Binary Search technique where we will be searching in a range of [1, N] iteratively by dividing the range halve every time until we get the resultant output.
Algorithm:
- Initialize two variables, left and right, to 0 and the given number, respectively.
- While left is less than or equal to right follow the below steps.
- Compute the mid point and cube value.
- If cube is equal to N then return N, else change the left and right pointers accordingly.
- If no perfect cube is found in the above steps, return false, indicating that the given number is not a perfect cube.
C++
#include <iostream> using namespace std; bool isPerfectCube( int num) { long left = 0; long right = num; while (left <= right) { long mid = left + (right - left) / 2; long cube = mid * mid * mid; if (cube == num) { return true ; } else if (cube < num) { left = mid + 1; } else { right = mid - 1; } } return false ; } int main() { if (isPerfectCube(729)) cout << "Yes" << endl; else cout << "No" << endl; return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { public static void main(String[] args) { if (isPerfectCube( 729 )) System.out.println( "Yes" ); else System.out.println( "No" ); } public static boolean isPerfectCube( int num) { long left = 0 ; long right = num; while (left <= right) { long mid = left + (right - left) / 2 ; long cube = mid * mid * mid; if (cube == num) { return true ; } else if (cube < num) { left = mid + 1 ; } else { right = mid - 1 ; } } return false ; } } |
Python3
def is_perfect_cube(num): left = 0 right = num while left < = right: mid = left + (right - left) / / 2 cube = mid * mid * mid if cube = = num: return True elif cube < num: left = mid + 1 else : right = mid - 1 return False if __name__ = = "__main__" : if is_perfect_cube( 729 ): print ( "Yes" ) else : print ( "No" ) |
C#
using System; class GFG { static bool IsPerfectCube( int num) { long left = 0; long right = num; while (left <= right) { long mid = left + (right - left) / 2; long cube = mid * mid * mid; if (cube == num) { return true ; } else if (cube < num) { left = mid + 1; } else { right = mid - 1; } } return false ; } static void Main( string [] args) { if (IsPerfectCube(729)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } |
Javascript
function isPerfectCube(num) { let left = 0; let right = num; while (left <= right) { let mid = left + Math.floor((right - left) / 2); let cube = mid * mid * mid; if (cube === num) { return true ; } else if (cube < num) { left = mid + 1; } else { right = mid - 1; } } return false ; } // Driver code if (isPerfectCube(729)) { console.log( "Yes" ); } else { console.log( "No" ); } |
Yes
Time Complexity : O(logN) [Binary Search]
Auxiliary Space : O(1)
Contact Us