Dados tres números enteros L, R y K, la tarea es encontrar el número de números enteros entre L y R, que son potencia perfecta de K. Ese es el número de números enteros que tienen la forma de K , donde a puede ser cualquier número.
Ejemplos:
Entrada: L = 3, R = 16, K = 3
Salida: 1
Explicación:
Solo hay un número entero entre 3 y 16 que está en el K que es 8.Entrada: L = 7, R = 18, K = 2
Salida: 2
Explicación:
Hay dos números que tienen forma de K y están en el rango de 7 a 18, que es 9 y 16.
Planteamiento: La idea es encontrar la raíz K -ésima de L y R respectivamente, donde la raíz K -ésima de un número N es un número real que da N, cuando lo elevamos a la potencia entera N. Entonces el conteo de enteros que son la potencia de K en el rango L y R se puede definir como:
Count = ( floor(Kthroot(R)) - ceil(Kthroot(L)) + 1 )
La raíz k -ésima de un número N se puede calcular usando las fórmulas de Newton , donde la iteración i se puede calcular usando las fórmulas a continuación:
x(i + 1) = (1 / K) * ((K – 1) * x(i) + N / x(i) ^ (N – 1))
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// count of numbers those are
// powers of K in range L to R
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// Nth root of the number
double nthRoot(int A, int N)
{
// initially guessing a random
// number between 0 to 9
double xPre = rand() % 10;
// Smaller eps,
// denotes more accuracy
double eps = 1e-3;
// Initializing difference between two
// roots by INT_MAX
double delX = INT_MAX;
// xK denotes
// current value of x
double xK;
// loop until we reach desired accuracy
while (delX > eps) {
// calculating current value
// from previous value
xK = ((N - 1.0) * xPre +
(double)A / pow(xPre, N - 1))
/ (double)N;
delX = abs(xK - xPre);
xPre = xK;
}
return xK;
}
// Function to count the perfect
// powers of K in range L to R
int countPowers(int a, int b, int k)
{
return (floor(nthRoot(b, k)) -
ceil(nthRoot(a, k)) + 1);
}
// Driver code
int main()
{
int a = 7, b = 28, k = 2;
cout << "Count of Powers is "
<< countPowers(a, b, k);
return 0;
}
Java
// Java implementation to find the
// count of numbers those are
// powers of K in range L to R
class GFG{
// Function to find the
// Nth root of the number
static double nthRoot(int A, int N)
{
// initially guessing a random
// number between 0 to 9
double xPre = Math.random()*10 % 10;
// Smaller eps,
// denotes more accuracy
double eps = 1e-3;
// Initializing difference between two
// roots by Integer.MAX_VALUE
double delX = Integer.MAX_VALUE;
// xK denotes
// current value of x
double xK = 0;
// loop until we reach desired accuracy
while (delX > eps)
{
// calculating current value
// from previous value
xK = ((N - 1.0) * xPre +
(double)A / Math.pow(xPre, N - 1))
/ (double)N;
delX = Math.abs(xK - xPre);
xPre = xK;
}
return xK;
}
// Function to count the perfect
// powers of K in range L to R
static int countPowers(int a, int b, int k)
{
return (int) (Math.floor(nthRoot(b, k)) -
Math.ceil(nthRoot(a, k)) + 1);
}
// Driver code
public static void main(String[] args)
{
int a = 7, b = 28, k = 2;
System.out.print("Count of Powers is "
+ countPowers(a, b, k));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 implementation to find the
# count of numbers those are
# powers of K in range L to R
import sys
from math import pow,ceil,floor
import random
# Function to find the
# Nth root of the number
def nthRoot(A,N):
# initially guessing a random
# number between 0 to 9
xPre = (random.randint(0, 9))%10
# Smaller eps,
# denotes more accuracy
eps = 1e-3
# Initializing difference between two
# roots by INT_MAX
delX = sys.maxsize
# xK denotes
# current value of x
# loo3p until we reach desired accuracy
while (delX > eps):
# calculating current value
# from previous value
xK = ((N - 1.0) * xPre + A / pow(xPre, N - 1))/ N
delX = abs(xK - xPre)
xPre = xK
return xK
# Function to count the perfect
# powers of K in range L to R
def countPowers(a, b, k):
return (floor(nthRoot(b, k)) - ceil(nthRoot(a, k)) + 1)
# Driver code
if __name__ == '__main__':
a = 7
b = 28
k = 2
print("Count of Powers is",countPowers(a, b, k))
# This code is contributed by Surendra_Gangwar
C#
// C# implementation to find the
// count of numbers those are
// powers of K in range L to R
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the
// Nth root of the number
static double nthRoot(int A, int N)
{
// initially guessing a random
// number between 0 to 9
Random r = new Random();
double xPre = r.Next(0,9);
// Smaller eps,
// denotes more accuracy
double eps = 1e-3;
// Initializing difference between two
// roots by int.MaxValue
double delX = int.MaxValue;
// xK denotes
// current value of x
double xK = 0;
// loop until we reach desired accuracy
while (delX > eps)
{
// calculating current value
// from previous value
xK = ((N - 1.0) * xPre +
(double)A / Math.Pow(xPre, N - 1))
/ (double)N;
delX = Math.Abs(xK - xPre);
xPre = xK;
}
return xK;
}
// Function to count the perfect
// powers of K in range L to R
static int countPowers(int a, int b, int k)
{
return (int) (Math.Floor(nthRoot(b, k)) -
Math.Ceiling(nthRoot(a, k)) + 1);
}
// Driver code
public static void Main(String[] args)
{
int a = 7, b = 28, k = 2;
Console.Write("Count of Powers is "
+ countPowers(a, b, k));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// JavaScript implementation to find the
// count of numbers those are
// powers of K in range L to R
// Function to find the
// Nth root of the number
function nthRoot(A, N)
{
// initially guessing a random
// number between 0 to 9
var xPre = Math.random() % 10;
// Smaller eps,
// denotes more accuracy
var eps = 0.001;
// Initializing difference between two
// roots by INT_MAX
var delX = 1000000000;
// xK denotes
// current value of x
var xK;
// loop until we reach desired accuracy
while (delX > eps) {
// calculating current value
// from previous value
xK = ((N - 1.0) * xPre +
A / Math.pow(xPre, N - 1))
/ N;
delX = Math.abs(xK - xPre);
xPre = xK;
}
return xK;
}
// Function to count the perfect
// powers of K in range L to R
function countPowers(a, b, k)
{
return (Math.floor(nthRoot(b, k)) -
Math.ceil(nthRoot(a, k)) + 1);
}
// Driver code
var a = 7, b = 28, k = 2;
document.write("Count of Powers is "
+ countPowers(a, b, k));
</script>
Producción
Count of Powers is 3
Análisis de rendimiento:
- Complejidad de tiempo: como en el enfoque anterior, hay dos llamadas de función para encontrar la raíz N del número que toma el tiempo O (logN), por lo tanto, la complejidad del tiempo será O (logN) .
- Complejidad espacial: como en el enfoque anterior, no se utiliza espacio adicional, por lo que la complejidad espacial será O(1) .