Valor mínimo de la raíz K-ésima de un número utilizando la búsqueda binaria recursiva

Posted on by Rudeus Greyrat

Dados dos números N y K , la tarea es encontrar el valor mínimo de la raíz K-ésima del número N . 
La raíz K-ésima del piso de un número N es el mayor número entero que es menor o igual que su raíz K -ésima.
Ejemplos: 
 

Entrada: N = 27, K = 3 
Salida: 3 
Explicación: 
K-ésima raíz de 27 = 3. Por lo tanto, 3 es el mayor número entero menor que igual a la K-ésima raíz de 27. 
Entrada: N = 36, K = 3 
Salida: 3 
Explicación : 
K-ésima raíz de 36 = 3,30 
Por lo tanto, 3 es el mayor número entero menor que igual a K-ésima raíz de 36 (3,30) 
 

Enfoque ingenuo: la idea es encontrar la K-ésima potencia de los números del 1 al N hasta que la K-ésima potencia de algún número K sea mayor que N. Entonces, el valor de (K – 1) será el valor mínimo de la raíz K-ésima de N. 
A continuación se muestra el algoritmo para resolver este problema utilizando el enfoque Naive: 
 

  • Iterar un ciclo desde los números 1 a N en K.
  • Para cualquier K, si su potencia K-ésima se vuelve mayor que N, entonces K-1 es el valor mínimo de la raíz K-ésima de N.

Complejidad de tiempo: O(√N)
Enfoque eficiente: 
Desde el enfoque Naive, está claro que el valor mínimo de la raíz K-ésima de N estará en el rango [1, N] . Por lo tanto, en lugar de verificar cada número en este rango, podemos buscar de manera eficiente el número requerido en este rango utilizando la búsqueda binaria . 
A continuación se muestra el algoritmo recursivo para resolver el problema anterior mediante la búsqueda binaria : 
 

  1. Implemente la búsqueda binaria en el rango de 0 a N.
  2. Encuentre el valor medio del rango usando la fórmula: 
     
mid = (start + end) / 2
  1.  
  2. Caso base: la llamada recursiva se ejecutará hasta que la K-ésima potencia de mid sea menor o igual a N y la K-ésima potencia de  (mid+1) sea mayor que igual a N.
     
(midK ≤ N) and ((mid + 1)K > N)
  1.  
  2. Si el caso base no se cumple, el rango se cambiará en consecuencia. 
    • Si la K-ésima potencia de mid es menor que igual a N , entonces el rango se actualiza a [mid + 1, end] 
       
if(midK ≤ N)
    updated range = [mid + 1, end]
  •  
  • Si la K-ésima potencia de mid es mayor que N , entonces el rango se actualiza a [low, mid + 1] 
     
if(midK > N)
    updated range = [low, mid - 1]
  •  

A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate x raised
// to the power y in O(logn)
int power(int x, unsigned int y)
{
    int temp;
    if (y == 0)
        return 1;
    temp = power(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else
        return x * temp * temp;
}
 
// Function to find the Kth
// root of the number N using BS
int nthRootSearch(int low, int high,
                  int N, int K)
{
 
    // If the range is still valid
    if (low <= high) {
 
        // Find the mid-value of range
        int mid = (low + high) / 2;
 
        // Base Case
        if ((power(mid, K) <= N)
            && (power(mid + 1, K) > N)) {
            return mid;
        }
 
        // Condition to check if the
        // left search space is useless
        else if (power(mid, K) < N) {
            return nthRootSearch(mid + 1,
                                 high, N, K);
        }
        else {
            return nthRootSearch(low,
                                 mid - 1,
                                 N, K);
        }
    }
    return low;
}
 
// Driver Code
int main()
{
 
    // Given N and K
    int N = 16, K = 4;
 
    // Function Call
    cout << nthRootSearch(0, N, N, K)
         << endl;
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
// Function to calculate x raised
// to the power y in O(logn)
static int power(int x, int y)
{
    int temp;
    if (y == 0)
        return 1;
         
    temp = power(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else
        return x * temp * temp;
}
 
// Function to find the Kth
// root of the number N using BS
static int nthRootSearch(int low, int high,
                         int N, int K)
{
     
    // If the range is still valid
    if (low <= high)
    {
         
        // Find the mid-value of range
        int mid = (low + high) / 2;
         
        // Base Case
        if ((power(mid, K) <= N) &&
            (power(mid + 1, K) > N))
        {
            return mid;
        }
         
        // Condition to check if the
        // left search space is useless
        else if (power(mid, K) < N)
        {
            return nthRootSearch(mid + 1,
                                 high, N, K);
        }
        else
        {
            return nthRootSearch(low,
                                 mid - 1, N, K);
        }
    }
    return low;
}
 
// Driver Code
public static void main(String s[])
{
     
    // Given N and K
    int N = 16, K = 4;
 
    // Function Call
    System.out.println(nthRootSearch(0, N, N, K));
}
}
 
// This code is contributed by rutvik_56

Python3

# Python3 program for the above approach
 
# Function to calculate x raised
# to the power y in O(logn)
def power(x, y):
 
    if (y == 0):
        return 1;
    temp = power(x, y // 2);
    if (y % 2 == 0):
        return temp * temp;
    else:
        return x * temp * temp;
 
# Function to find the Kth
# root of the number N using BS
def nthRootSearch(low, high, N, K):
 
    # If the range is still valid
    if (low <= high):
 
        # Find the mid-value of range
        mid = (low + high) // 2;
 
        # Base Case
        if ((power(mid, K) <= N) and
            (power(mid + 1, K) > N)):
            return mid;
 
        # Condition to check if the
        # left search space is useless
        elif (power(mid, K) < N):
            return nthRootSearch(mid + 1,
                                 high, N, K);
        else:
            return nthRootSearch(low,
                                 mid - 1,
                                 N, K);
     
    return low;
 
# Driver Code
 
# Given N and K
N = 16; K = 4;
 
# Function Call
print(nthRootSearch(0, N, N, K))
 
# This code is contributed by Code_Mech

C#

// C# program for the above approach
using System;
class GFG{
 
// Function to calculate x raised
// to the power y in O(logn)
static int power(int x, int y)
{
    int temp;
    if (y == 0)
        return 1;
         
    temp = power(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else
        return x * temp * temp;
}
 
// Function to find the Kth
// root of the number N using BS
static int nthRootSearch(int low, int high,
                         int N, int K)
{
     
    // If the range is still valid
    if (low <= high)
    {
         
        // Find the mid-value of range
        int mid = (low + high) / 2;
         
        // Base Case
        if ((power(mid, K) <= N) &&
            (power(mid + 1, K) > N))
        {
            return mid;
        }
         
        // Condition to check if the
        // left search space is useless
        else if (power(mid, K) < N)
        {
            return nthRootSearch(mid + 1,
                                 high, N, K);
        }
        else
        {
            return nthRootSearch(low,
                                 mid - 1, N, K);
        }
    }
    return low;
}
 
// Driver Code
public static void Main()
{
     
    // Given N and K
    int N = 16, K = 4;
 
    // Function Call
    Console.Write(nthRootSearch(0, N, N, K));
}
}
 
// This code is contributed by Code_Mech

Javascript

<script>
 
// JavaScript program to implement
// the above approach
  
// Function to calculate x raised
// to the power y in O(logn)
function power(x, y)
{
    let temp;
    if (y == 0)
        return 1;
          
    temp = power(x, Math.floor(y / 2));
    if (y % 2 == 0)
        return temp * temp;
    else
        return x * temp * temp;
}
  
// Function to find the Kth
// root of the number N using BS
function nthRootSearch(low, high,
                         N, K)
{
      
    // If the range is still valid
    if (low <= high)
    {
          
        // Find the mid-value of range
        let mid = Math.floor((low + high) / 2);
          
        // Base Case
        if ((power(mid, K) <= N) &&
            (power(mid + 1, K) > N))
        {
            return mid;
        }
          
        // Condition to check if the
        // left search space is useless
        else if (power(mid, K) < N)
        {
            return nthRootSearch(mid + 1,
                                 high, N, K);
        }
        else
        {
            return nthRootSearch(low,
                                 mid - 1, N, K);
        }
    }
    return low;
}
 
// Driver code
 
    // Given N and K
    let N = 16, K = 4;
  
    // Function Call
    document.write(nthRootSearch(0, N, N, K));
  
 // This code is contributed by sanjoy_62.
</script>
Producción: 

2

 

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por spp____ 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 *