Dado un número N , la tarea es escribir un programa en C para verificar si el número dado es un cubo perfecto o no .
Entrada: N = 216
Salida: Sí
Explicación:
Como 216 = 6*6*6.
Por lo tanto, la raíz cúbica de 216 es 6.Entrada: N = 100
Salida: No
Método 1: Enfoque ingenuo Para encontrar la raíz cúbica del número dado, itere sobre todos los números naturales desde 1 hasta N y verifique si el cubo de cualquier número en este rango es igual al número N dado , luego imprima Sí , de lo contrario imprima No
A continuación se muestra la implementación del enfoque anterior:
C
// C program for the above approach #include <math.h> #include <stdio.h> // Function to check if a number is // a perfect Cube void perfectCube(int N) { for (int i = 1; i < N; i++) { // If cube of i is equals to N // then print Yes and return if (i * i * i == N) { printf("Yes"); return; } } // No number was found whose cube // is equal to N printf("No"); return; } // Driver Code int main() { // Given Number int N = 216; // Function Call perfectCube(N); return 0; }
Yes
Análisis de Complejidad:
- Complejidad de tiempo: O(N), solo se necesita un recorrido de la solución, por lo que la complejidad de tiempo es O(N).
- Espacio Auxiliar: O(1). Se necesita espacio adicional constante.
Método 2: Usar la función incorporada La idea es usar el valor mínimo de la función incorporada N N N N
A continuación se muestra la implementación del enfoque anterior:
C
// C program for the above approach #include <math.h> #include <stdio.h> // Function to check if a number is // perfect cube using inbuilt function void perfectCube(int N) { int cube_root; cube_root = (int)round(pow(N, 1.0 / 3.0)); // If cube of cube_root is equals // to N, then print Yes else No if (cube_root * cube_root * cube_root == N) { printf("Yes"); return; } else { printf("No"); return; } } // Driver Code int main() { // Given number N int N = 216; // Function Call perfectCube(N); return 0; }
Yes
Análisis de Complejidad:
- Complejidad de tiempo: O(N), ya que la función pow() funciona en O(N), por lo que la complejidad de tiempo es O(N).
- Espacio Auxiliar: O(1). Se necesita espacio adicional constante.
Método 3: Uso de la búsqueda binaria La idea es utilizar la búsqueda binaria
- Inicialice low y high como 0 y N respectivamente.
- Iterar hasta bajo ≤ alto y hacer lo siguiente:
- Encuentre el valor de mid como = (low + high)/2 .
- Compruebe si mid*mid*mid es igual a N y luego imprima «Sí» .
- Si el cubo de mid es menor que N , busque un valor mayor en la segunda mitad del espacio de búsqueda actualizando low to mid + 1.
- Si el cubo de mid es mayor que N , busque un valor más pequeño en la primera mitad del espacio de búsqueda actualizando high to mid – 1.
- Si no se obtiene el cubo de N en el paso anterior, imprima «No» .
A continuación se muestra la implementación del enfoque anterior:
C
// C program for the above approach #include <math.h> #include <stdio.h> // Function to check if a number is // a perfect Cube using binary search void perfectCube(int N) { int start = 1, end = N; while (start <= end) { // Calculating mid int mid = (start + end) / 2; // If N is a perfect cube if (mid * mid * mid == N) { printf("Yes"); return; } // If mid^3 is smaller than N, // then move closer to cube // root of N if (mid * mid * mid < N) { start = mid + 1; } // If mid^3 is greater than N else end = mid - 1; } printf("No"); return; } // Driver Code int main() { // Given Number N int N = 216; // Function Call perfectCube(N); return 0; }
Yes
Análisis de Complejidad:
- Complejidad temporal: O(log N). La complejidad temporal de la búsqueda binaria es O(log N).
- Espacio Auxiliar: O(1). Se necesita espacio adicional constante.
Publicación traducida automáticamente
Artículo escrito por chandan_kr y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA