Programa C para verificar si un número es un cubo perfecto o no

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:
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 , 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;
}
Producción:

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;
}
Producción:

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

  1. Inicialice low y high como 0 y N respectivamente.
  2. 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.
  3. 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;
}
Producción:

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *