Dada una array arr[] con N enteros no negativos, la tarea es encontrar el número de elementos que son K-ésimas potencias de sus índices, donde K es un número no negativo.
arr[i] = i K
Ejemplo:
Entrada: arr = [1, 1, 4, 3, 16, 125, 1], K = 0
Salida: 3
Explicación: 3 elementos son késimas potencias de sus índices:
0 0 es 1, 1 0 es 1 y 6 0 es 1Entrada: arr = [0, 1, 4, 3], K = 2
Salida: 2
Explicación: 0 2 es 0, 1 2 es 1 y 2 2 es 4
Enfoque: el problema dado se puede resolver encontrando las K-ésimas potencias de cada índice y verificando si son iguales al elemento presente en ese índice. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable res a 0 para almacenar la respuesta
- Si el valor de K es 0:
- Si el primer elemento en la array arr existe y es igual a 1, entonces incremente res en 1
- De lo contrario, si el valor de K es mayor que 0:
- Si el primer elemento en la array arr existe y es igual a 0, incremente res en 1
- Si el segundo elemento en la array arr existe y es igual a 1, entonces incremente res en 1
- Itere la array arr desde el índice 2 hasta el final y en cada índice:
- Inicialice una variable indPow al índice actual i y multiplíquelo por i, k-1 veces
- Si el valor de indPow se vuelve igual al elemento actual arr[i] entonces incremente res en 1
- Devuelve res como nuestra respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find count of elements which
// are a non-negative power of their indices
int indPowEqualsEle(vector<int> arr, int K)
{
// Length of the array
int len = arr.size();
// Initialize variable res for
// calculating the answer
int res = 0;
// If the value of K is 0
if (K == 0)
{
// If the first element is 1
// then the condition is satisfied
if (len > 0 && arr[0] == 1)
res++;
}
// If the value of K > 0
if (K > 0)
{
// If the first is 0 increment res
if (len > 0 && arr[0] == 1)
res++;
}
// If the second element is 1
// then increment res
if (len > 1 && arr[1] == 1)
res++;
// Iterate the array arr from index 2
for (int i = 2; i < len; i++)
{
// Initialize a variable
// to index which is to be
// multiplied K-1 times
long indPow = i;
for (int j = 2; j < K; j++)
{
// Multiply current value
// with index K - 1 times
indPow *= i;
}
// If index power K is equal to
// the element then increment res
if (indPow == arr[i])
res++;
}
// return the result
return res;
}
// Driver function
int main()
{
// Initialize an array
vector<int> arr = {1, 1, 4, 3, 16, 125, 1};
// Initialize power
int K = 0;
// Call the function
// and print the answer
cout << (indPowEqualsEle(arr, K));
return 0;
}
// This code is contributed by Potta Lokesh
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find count of elements which
// are a non-negative power of their indices
public static int
indPowEqualsEle(int[] arr, int K)
{
// Length of the array
int len = arr.length;
// Initialize variable res for
// calculating the answer
int res = 0;
// If the value of K is 0
if (K == 0) {
// If the first element is 1
// then the condition is satisfied
if (len > 0 && arr[0] == 1)
res++;
}
// If the value of K > 0
if (K > 0) {
// If the first is 0 increment res
if (len > 0 && arr[0] == 1)
res++;
}
// If the second element is 1
// then increment res
if (len > 1 && arr[1] == 1)
res++;
// Iterate the array arr from index 2
for (int i = 2; i < len; i++) {
// Initialize a variable
// to index which is to be
// multiplied K-1 times
long indPow = i;
for (int j = 2; j < K; j++) {
// Multiply current value
// with index K - 1 times
indPow *= i;
}
// If index power K is equal to
// the element then increment res
if (indPow == arr[i])
res++;
}
// return the result
return res;
}
// Driver function
public static void main(String[] args)
{
// Initialize an array
int[] arr = { 1, 1, 4, 3, 16, 125, 1 };
// Initialize power
int K = 0;
// Call the function
// and print the answer
System.out.println(
indPowEqualsEle(arr, K));
}
}
Python3
# python code for the above approach # Function to find count of elements which # are a non-negative power of their indices def indPowEqualsEle(arr, K): # Length of the array le = len(arr) # Initialize variable res for # calculating the answer res = 0 # If the value of K is 0 if (K == 0): # If the first element is 1 # then the condition is satisfied if (le > 0 and arr[0] == 1): res += 1 # If the value of K > 0 if (K > 0): # If the first is 0 increment res if (le > 0 and arr[0] == 1): res += 1 # If the second element is 1 # then increment res if (le > 1 and arr[1] == 1): res += 1 # Iterate the array arr from index 2 for i in range(2, le): # Initialize a variable # to index which is to be # multiplied K-1 times indPow = i for j in range(2, K): # Multiply current value # with index K - 1 times indPow *= i # If index power K is equal to # the element then increment res if (indPow == arr[i]): res += 1 # return the result return res # Driver function if __name__ == "__main__": # Initialize an array arr = [1, 1, 4, 3, 16, 125, 1] # Initialize power K = 0 # Call the function # and print the answer print(indPowEqualsEle(arr, K)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG
{
// Function to find count of elements which
// are a non-negative power of their indices
static int indPowEqualsEle(int []arr, int K)
{
// Length of the array
int len = arr.Length;
// Initialize variable res for
// calculating the answer
int res = 0;
// If the value of K is 0
if (K == 0)
{
// If the first element is 1
// then the condition is satisfied
if (len > 0 && arr[0] == 1)
res++;
}
// If the value of K > 0
if (K > 0)
{
// If the first is 0 increment res
if (len > 0 && arr[0] == 1)
res++;
}
// If the second element is 1
// then increment res
if (len > 1 && arr[1] == 1)
res++;
// Iterate the array arr from index 2
for (int i = 2; i < len; i++)
{
// Initialize a variable
// to index which is to be
// multiplied K-1 times
long indPow = i;
for (int j = 2; j < K; j++)
{
// Multiply current value
// with index K - 1 times
indPow *= i;
}
// If index power K is equal to
// the element then increment res
if (indPow == arr[i])
res++;
}
// return the result
return res;
}
// Driver Code
public static void Main()
{
// Initialize an array
int []arr = {1, 1, 4, 3, 16, 125, 1};
// Initialize power
int K = 0;
// Call the function
// and print the answer
Console.Write(indPowEqualsEle(arr, K));
}
}
// This code is contributed by Samim Hossain Mondal
Javascript
//<script>
// Javascript program for the above approach
// Function to find count of elements which
// are a non-negative power of their indices
function indPowEqualsEle(arr, K)
{
// Length of the array
let len = arr.length;
// Initialize variable res for
// calculating the answer
let res = 0;
// If the value of K is 0
if (K == 0)
{
// If the first element is 1
// then the condition is satisfied
if (len > 0 && arr[0] == 1)
res++;
}
// If the value of K > 0
if (K > 0)
{
// If the first is 0 increment res
if (len > 0 && arr[0] == 1)
res++;
}
// If the second element is 1
// then increment res
if (len > 1 && arr[1] == 1)
res++;
// Iterate the array arr from index 2
for (let i = 2; i < len; i++)
{
// Initialize a variable
// to index which is to be
// multiplied K-1 times
let indPow = i;
for (let j = 2; j < K; j++)
{
// Multiply current value
// with index K - 1 times
indPow *= i;
}
// If index power K is equal to
// the element then increment res
if (indPow == arr[i])
res++;
}
// return the result
return res;
}
// Driver Code
// Initialize an array
let arr = [ 1, 1, 4, 3, 16, 125, 1 ];
// Initialize power
let K = 0;
// Call the function
// and print the answer
document.write(indPowEqualsEle(arr, K));
// This code is contributed by Samim Hossain Mondal
</script>
Producción
3
Complejidad temporal: O(N * K)
Espacio auxiliar: O(1)