Dada una array arr[] de tamaño N y un entero K , la tarea es imprimir todos los elementos de la array que se pueden expresar como una potencia de algún número entero (X) al exponente K, es decir , X K.
Ejemplos:
Entrada: arr[] = {46656, 64, 256, 729, 16, 1000}, K = 6
Salida: 46656 64 729
Explicación:
solo los números 46656, 64, 729 se pueden expresar como una potencia de 6.
46656 = 6 6 ,
64 = 2 6 ,
729 = 3 6
Entrada: arr[] = {23, 81, 256, 125, 16, 1000}, K = 4
Salida: 81 256 16
Explicación:
El número 81, 256, 16 se puede expresar como una potencia de 4.
Enfoque: Para resolver el problema mencionado anteriormente, la idea principal es encontrar la raíz N-ésima de un número para cada número en el Array . Luego verifica si este número es un número entero o no. En caso afirmativo, imprímalo, de lo contrario, pase al siguiente número.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation to print elements of
// the Array which can be expressed as
// power of some integer to given exponent K
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Method returns Nth power of A
double nthRoot(ll A, ll N)
{
double xPre = 7;
// Smaller eps, denotes more accuracy
double eps = 1e-3;
// Initializing difference between two
// roots by INT_MAX
double delX = INT_MAX;
// x^K denotes current value of x
double xK;
// loop untill we reach desired accuracy
while (delX > eps) {
// calculating current value from previous
// value by newton's method
xK = ((N - 1.0) * xPre
+ (double)A / pow(xPre, N - 1))
/ (double)N;
delX = abs(xK - xPre);
xPre = xK;
}
return xK;
}
// Function to check
// whether its k root
// is an integer or not
bool check(ll no, int k)
{
double kth_root = nthRoot(no, k);
ll num = kth_root;
if (abs(num - kth_root) < 1e-4)
return true;
return false;
}
// Function to find the numbers
void printExpo(ll arr[], int n, int k)
{
for (int i = 0; i < n; i++) {
if (check(arr[i], k))
cout << arr[i] << " ";
}
}
// Driver code
int main()
{
int K = 6;
ll arr[] = { 46656, 64, 256,
729, 16, 1000 };
int n = sizeof(arr) / sizeof(arr[0]);
printExpo(arr, n, K);
return 0;
}
Java
// Java implementation to print elements of
// the Array which can be expressed as
// power of some integer to given exponent K
class GFG{
// Method returns Nth power of A
static double nthRoot(long A, long N)
{
double xPre = 7;
// Smaller eps, denotes more accuracy
double eps = 1e-3;
// Initializing difference between two
// roots by Integer.MAX_VALUE
double delX = Integer.MAX_VALUE;
// x^K denotes current value of x
double xK = 0;
// loop untill we reach desired accuracy
while (delX > eps) {
// calculating current value from previous
// value by newton's method
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 check
// whether its k root
// is an integer or not
static boolean check(long no, int k)
{
double kth_root = nthRoot(no, k);
long num = (long) kth_root;
if (Math.abs(num - kth_root) < 1e-4)
return true;
return false;
}
// Function to find the numbers
static void printExpo(long arr[], int n, int k)
{
for (int i = 0; i < n; i++) {
if (check(arr[i], k))
System.out.print(arr[i]+ " ");
}
}
// Driver code
public static void main(String[] args)
{
int K = 6;
long arr[] = { 46656, 64, 256,
729, 16, 1000 };
int n = arr.length;
printExpo(arr, n, K);
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 implementation to print elements of # the Array which can be expressed as # power of some integer to given exponent K # Method returns Nth power of A def nthRoot(A, N): xPre = 7 # Smaller eps, denotes more accuracy eps = 1e-3 # Initializing difference between two # roots by INT_MAX delX = 10**9 # x^K denotes current value of x xK = 0 # loop until we reach desired accuracy while (delX > eps): # calculating current value from previous # value by newton's method xK = ((N - 1.0) * xPre+ A /pow(xPre, N - 1))/ N delX = abs(xK - xPre) xPre = xK return xK # Function to check # whether its k root # is an integer or not def check(no, k): kth_root = nthRoot(no, k) num = int(kth_root) if (abs(num - kth_root) < 1e-4): return True return False # Function to find the numbers def printExpo(arr, n, k): for i in range(n): if (check(arr[i], k)): print(arr[i],end=" ") # Driver code if __name__ == '__main__': K = 6 arr = [46656, 64, 256,729, 16, 1000] n = len(arr) printExpo(arr, n, K) # This code is contributed by mohit kumar 29
C#
// C# implementation to print elements of
// the Array which can be expressed as
// power of some integer to given exponent K
using System;
class GFG{
// Method returns Nth power of A
static double nthRoot(long A, long N)
{
double xPre = 7;
// Smaller eps, denotes more accuracy
double eps = 1e-3;
// Initializing difference between two
// roots by int.MaxValue
double delX = int.MaxValue;
// x^K denotes current value of x
double xK = 0;
// loop untill we reach desired accuracy
while (delX > eps) {
// calculating current value from previous
// value by newton's method
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 check
// whether its k root
// is an integer or not
static bool check(long no, int k)
{
double kth_root = nthRoot(no, k);
long num = (long) kth_root;
if (Math.Abs(num - kth_root) < 1e-4)
return true;
return false;
}
// Function to find the numbers
static void printExpo(long []arr, int n, int k)
{
for (int i = 0; i < n; i++) {
if (check(arr[i], k))
Console.Write(arr[i]+ " ");
}
}
// Driver code
public static void Main(String[] args)
{
int K = 6;
long []arr = { 46656, 64, 256,
729, 16, 1000 };
int n = arr.Length;
printExpo(arr, n, K);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation to print elements of
// the Array which can be expressed as
// power of some integer to given exponent K
// Method returns Nth power of A
function nthRoot(A,N)
{
let xPre = 7;
// Smaller eps, denotes more accuracy
let eps = 1e-3;
// Initializing difference between two
// roots by Integer.MAX_VALUE
let delX = Number.MAX_VALUE;
// x^K denotes current value of x
let xK = 0;
// loop untill we reach desired accuracy
while (delX > eps) {
// calculating current value from previous
// value by newton's method
xK = ((N - 1.0) * xPre
+ A / Math.pow(xPre, N - 1))
/ N;
delX = Math.abs(xK - xPre);
xPre = xK;
}
return xK;
}
// Function to check
// whether its k root
// is an integer or not
function check(no,k)
{
let kth_root = nthRoot(no, k);
let num = Math.floor(kth_root);
if (Math.abs(num - kth_root) < 1e-4)
return true;
return false;
}
// Function to find the numbers
function printExpo(arr,n,k)
{
for (let i = 0; i < n; i++) {
if (check(arr[i], k))
document.write(arr[i]+ " ");
}
}
// Driver code
let K = 6;
let arr=[46656, 64, 256,
729, 16, 1000];
let n = arr.length;
printExpo(arr, n, K);
// This code is contributed by patel2127
</script>
Producción:
46656 64 729