Dado un número N, la tarea es encontrar el número de cuadrados perfectos y cubos perfectos desde 1 hasta un número entero dado, N (ambos inclusive).
Nota: Los números que son cuadrados perfectos y cubos perfectos deben contarse una vez.
Ejemplos:
Entrada: N = 70
Salida: 10
Explicación: Números que son cuadrados perfectos o cubos perfectos
1, 4, 8, 9, 16, 25, 27, 36, 49, 64Entrada: N = 25
Salida: 6
Explicación: Números que son cuadrados perfectos o cubos perfectos
1, 4, 8, 9, 16, 25
Enfoque ingenuo:
Comprueba todos los números del 1 al N, si es un cuadrado o un cubo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach #include <iostream> #include <math.h> // For sqrt() and cbrt() using namespace std; // Function to check if the // number is a perfect square bool isSquare(int num) { int root = sqrt(num); return (root * root) == num; } // Function to check if the // number is a perfect cube bool isCube(int num) { int root = cbrt(num); return (root * root * root) == num; } // Function to count the number // of perfect squares and cubes int countSC(int N) { int count = 0; for (int i = 1; i <= N; i++) { // If a number is perfect square, if (isSquare(i)) count++; // Else if the number is cube or not else if (isCube(i)) count++; } return count; } // Driver code int main() { int N = 20; cout << "Number of squares and cubes is " << countSC(N); return 0; }
Java
// Java implementation of // above approach class GFG { // Function to check if the // number is a perfect square static boolean isSquare(int num) { int root = (int)Math.sqrt(num); return (root * root) == num; } // Function to check if the // number is a perfect cube static boolean isCube(int num) { int root = (int)Math.cbrt(num); return (root * root * root) == num; } // Function to count the number // of perfect squares and cubes static int countSC(int N) { int count = 0; for (int i = 1; i <= N; i++) { // If a number is perfect // square, if (isSquare(i)) count++; // Else if the number is // cube or not else if (isCube(i)) count++; } return count; } // Driver code public static void main(String[] args) { int N = 20; System.out.println("Number of squares " + "and cubes is " + countSC(N)); } } // This code is contributed // by ChitraNayal
Python3
# Python 3 implementation of # above approach # Function to check if the # number is a perfect square def isSquare(num): root = int(num ** (1 / 2)) return (root * root) == num # Function to check if the # number is a perfect cube def isCube(num): root = int(num ** (1 / 3)) return (root * root * root) == num # Function to count the number # of perfect squares and cubes def countSC(N): count = 0 for i in range(1, N + 1): # If a number is perfect square, if isSquare(i): count += 1 # Else if the number is cube elif isCube(i): count += 1 return count # Driver code if __name__ == "__main__": N = 20 print("Number of squares and cubes is ", countSC(N)) # This code is contributed by ANKITRAI1
C#
// C# implementation of // above approach using System; class GFG { // Function to check if the // number is a perfect square static bool isSquare(int num) { int root = (int)Math.Sqrt(num); return (root * root) == num; } // Function to check if the // number is a perfect cube static bool isCube(int num) { int root = (int)Math.Pow(num, (1.0 / 3.0)); return (root * root * root) == num; } // Function to count the number // of perfect squares and cubes static int countSC(int N) { int count = 0; for (int i = 1; i <= N; i++) { // If a number is perfect // square, if (isSquare(i)) count++; // Else if the number is // cube or not else if (isCube(i)) count++; } return count; } // Driver code public static void Main() { int N = 20; Console.Write("Number of squares and " + "cubes is " + countSC(N)); } } // This code is contributed // by ChitraNayal
PHP
<?php // PHP implementation of above approach // Function to check if the // number is a perfect square function isSquare($num) { $root = (int)sqrt($num); return ($root * $root) == $num; } // Function to check if the // number is a perfect cube function isCube($num) { $root = (int)pow($num, 1 / 3); return ($root * $root * $root) == $num; } // Function to count the number // of perfect squares and cubes function countSC($N) { $count = 0; for ($i = 1; $i <= $N; $i++) { // If a number is // perfect square, if (isSquare($i)) $count++; // Else if the number // is cube or not else if (isCube($i)) $count++; } return $count; } // Driver code $N = 20; echo "Number of squares and " . "cubes is " . countSC($N); // This code is contributed // by ChitraNayal ?>
Javascript
<script> // Javascript implementation of above approach // Function to check if the // number is a perfect square function isSquare(num) { let root = parseInt(Math.sqrt(num), 10); return (root * root) == num; } // Function to check if the // number is a perfect cube function isCube(num) { let root = parseInt(Math.cbrt(num), 10); return (root * root * root) == num; } // Function to count the number // of perfect squares and cubes function countSC(N) { let count = 0; for (let i = 1; i <= N; i++) { // If a number is perfect square, if (isSquare(i)) count++; // Else if the number is cube or not else if (isCube(i)) count++; } return count; } let N = 20; document.write("Number of squares and cubes is " + countSC(N)); </script>
Number of squares and cubes is 5
Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)
Enfoque eficiente:
- El número de cuadrados de 1 a N es floor(sqrt(N)) .
- El número de cubos de 1 a N es floor(cbrt(N)) .
- Elimine los números que son tanto cuadrados como cúbicos (como 1, 64….) restándole piso(sqrt(cbrt(N))) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach #include <iostream> #include <math.h> // For sqrt() and cbrt() using namespace std; // Function to count the number // of perfect squares and cubes int countSC(int N) { int res = (int)sqrt(N) + (int)cbrt(N) - (int)(sqrt(cbrt(N))); return res; } // Driver code int main() { int N = 20; cout << "Number of squares and cubes is " << countSC(N); return 0; }
Java
// Java implementation of // above approach class GFG { // Function to count the number // of perfect squares and cubes static int countSC(int N) { int res = (int)Math.sqrt(N) + (int)Math.cbrt(N) - (int)(Math.sqrt(Math.cbrt(N))); return res; } // Driver code public static void main(String[] args) { int N = 20; System.out.println("Number of squares " + "and cubes is " + countSC(N)); } } // This code is contributed // by ChitraNayal
Python3
# Python implementation of # above approach import math # for sqrt() # Function to count the number # of perfect squares and cubes def cr(N): if pow(round(N ** (1 / 3)), 3) == N: return round(N ** (1 / 3)) return int(N ** (1 / 3)) def countSC(N): res = (int(math.sqrt(N)) + int(cr(N)) - int(math.sqrt(cr(N)))) return res # Driver code N = 20 print("Number of squares and cubes is", countSC(N)) # This code is contributed # by vaibhav29498
C#
// C# implementation of // above approach using System; public class GFG { // Function to count the number // of perfect squares and cubes static int countSC(int N) { int res = (int)(Math.Sqrt(N) + Math.Ceiling( Math.Pow(N, (double)1 / 3)) - (Math.Sqrt(Math.Ceiling( Math.Pow(N, (double)1 / 3))))); return res; } // Driver code public static void Main() { int N = 20; Console.Write("Number of squares " + "and cubes is " + countSC(N)); } } /*This code is contributed by 29AjayKumar*/
PHP
<?php // PHP implementation of above approach // Function to count the number // of perfect squares and cubes function countSC($N) { $res = sqrt($N) + pow($N, 1 / 3) - (sqrt(pow($N, 1 / 3))); return floor($res); } // Driver code $N = 20; echo "Number of squares and cubes is " , countSC($N); // This code is contributed // by Shashank ?>
Javascript
<script> // Javascript implementation of above approach // Function to count the number // of perfect squares and cubes function countSC(N) { let res = parseInt(Math.sqrt(N), 10) + parseInt(Math.cbrt(N), 10) - parseInt(Math.sqrt(parseInt(Math.cbrt(N), 10)), 10); return res; } let N = 20; document.write("Number of squares and cubes is " + countSC(N)); </script>
Number of squares and cubes is 5
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)