Dados dos números N y K . La tarea es comprobar si N es la K -ésima potencia de cualquier número entero, es decir, si N se puede expresar como XK , donde X es un número entero.
Ejemplos:
Entrada: N = 81, K = 4
Salida: Verdadero
Explicación: 81 se puede expresar como 3 4Entrada: N = 26, K = 2
Salida: Falso
Explicación: 26 no se puede expresar como potencia de 2 a ningún númeroEntrada: N = 512, K = 3
Salida: Verdadero
Explicación: 512 se puede expresar 8 3
Enfoque ingenuo: para resolver este problema, podemos atravesar de 1 a N y comprobar si el número N es la K -ésima potencia del número actual.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: El enfoque eficiente para resolver el problema anterior se basa en la siguiente idea:
Digamos que el número N es la K-ésima potencia de algún entero X. Entonces,
N = X K
o X = N 1/K . Ahora bien, si X es un número entero, entonces la solución existe.Así que necesitamos encontrar si el piso de la raíz K -ésima de N es la raíz K -ésima real o no
Siga los pasos mencionados a continuación para implementar la idea:
- Compruebe si K es 0 o no. Si K es 0 y N = 1 , entonces es posible que N sea la K -ésima potencia de cualquier número.
- Almacene el recíproco de K (digamos x ) y luego encuentre la raíz x -ésima de N.
- Si tanto el valor máximo como el valor mínimo de la raíz x -ésima de N son iguales, entonces es posible que N sea la K -ésima parte de cualquier número.
- Si ninguna de las condiciones anteriores es cierta, entonces no es posible tal solución.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to check whether n is
// kth power of an integer
bool check_Kth_power(int n, int k)
{
// Checking for special case when k=0
if (k == 0) {
if (n == 1) {
return true;
}
return false;
}
else {
// Calculating reciprocal of k
double reciprocal = (double)(1) / (double)(k);
// The result for n^(1/k)
double result = pow(n, reciprocal);
// Checking condition for an integer
if (floor(result) == ceil(result)) {
return true;
}
return false;
}
}
// Driver Code
int main()
{
int N = 81;
int K = 4;
// Function call
bool ans = check_Kth_power(N, K);
if (ans)
cout << "True";
else
cout << "False";
return 0;
}
C
// C code to implement the approach
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
// Function to check whether n is kth power
// to an integer
bool check_Kth_power(int n, int k)
{
// Checking for special case when k=0
if (k == 0) {
if (n == 1) {
return true;
}
return false;
}
else {
// Calculating reciprocal of k
double reciprocal = (double)(1) / (double)(k);
// The result for n^(1/k)
double result = pow(n, reciprocal);
// Checking condition for an integer
if (floor(result) == ceil(result)) {
return true;
}
return false;
}
}
// Driver code
int main()
{
int N = 81;
int K = 4;
// Function call
bool ans = check_Kth_power(N, K);
if (ans == true)
printf("True");
else
printf("False");
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
import java.lang.Math;
class GFG {
// Function to check whether n is kth power
// to an integer
public static Boolean check_Kth_power(int n,
int k)
{
// Checking for special case when k=0
if (k == 0) {
if (n == 1) {
return true;
}
return false;
}
else {
// Calculating reciprocal of k
double reciprocal = (double)(1) / (double)(k);
// The result for n^(1/k)
double result = Math.pow(n, reciprocal);
// Checking condition for an integer
if (Math.floor(result) == Math.ceil(result)) {
return true;
}
return false;
}
}
// Driver code
public static void main(String[] args)
{
int N = 81;
int K = 4;
// Function call
Boolean ans = check_Kth_power(N, K);
if (ans == true)
System.out.println("True");
else
System.out.println("False");
}
}
Python3
# python code to implement the approach
import math
# Function to check whether n is
# kth power of an integer
def check_Kth_power( n, k):
# Checking for special case when k=0
if (k == 0):
if (n == 1):
return True
return False
else:
# Calculating reciprocal of k
reciprocal = (1) // (k)
# The result for n^(1/k)
result = n**reciprocal
# Checking condition for an integer
if math.floor(result) == math.ceil(result):
return True
return False
# Driver Code
N = 81
K = 4
# Function call
ans = check_Kth_power(N, K)
if (ans):
print("True")
else:
print("False")
# This code is contributed by rohitsingh07052.
C#
// C# code to implement the approach
using System;
public class GFG {
// Function to check whether n is kth power
// to an integer
static Boolean check_Kth_power(int n, int k)
{
// Checking for special case when k=0
if (k == 0) {
if (n == 1) {
return true;
}
return false;
}
else {
// Calculating reciprocal of k
double reciprocal = (double)(1) / (double)(k);
// The result for n^(1/k)
double result = Math.Pow(n, reciprocal);
// Checking condition for an integer
if (Math.Floor(result)
== Math.Ceiling(result)) {
return true;
}
return false;
}
}
// Driver Code
static public void Main()
{
int N = 81;
int K = 4;
// Function call
Boolean ans = check_Kth_power(N, K);
if (ans == true)
Console.WriteLine("True");
else
Console.WriteLine("False");
}
}
// This code is contributed by Rohit Pradhan
Javascript
<script>
// Function to check whether n is
// kth power of an integer
function check_Kth_power(n, k)
{
// Checking for special case when k=0
if (k == 0) {
if (n == 1) {
return true;
}
return false;
}
else {
// Calculating reciprocal of k
let reciprocal = 1 / k;
// The result for n^(1/k)
let result = Math.pow(n, reciprocal);
// Checking condition for an integer
if (Math.floor(result) == Math.ceil(result)) {
return true;
}
return false;
}
}
// Driver Code
let N = 81;
let K = 4;
// Function call
let ans = check_Kth_power(N, K);
if (ans)
console.log("True");
else
console.log("False");
// This code is contributed by shinjanpatra
</script>
True
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)