Dada una array arr[] con N enteros no negativos, encuentre el número máximo de elementos que son las mismas potencias no negativas de sus índices.
arr[i] = i X , donde X es un número no negativo.
La tarea es devolver la frecuencia máxima de X.
Ejemplo:
Entrada: arr = [1, 1, 4, 17]
Salida: 2
Explicación:
El elemento 1 en el índice 0, es una potencia de 0
El elemento 1 en el índice 1, es una potencia de 0
El elemento 4 en el índice 2, es una potencia de 2
El elemento 17 en el índice 3, no es una potencia de su índice, por lo que no se considera
Por lo tanto, la frecuencia máxima es de potencia 0, que es 2Entrada: arr = [0, 1, 1, 9, 1, 25]
Salida: 4
Explicación:
El elemento 0 en índice 0, es una potencia de 2
El elemento 1 en índice 1, es una potencia de 2
El elemento 1 en índice 2, es una potencia de 0
El elemento 9 de índice 3, es una potencia de 2
El elemento 1 de índice 4, es una potencia de 0
El elemento 25 de índice 5, es una potencia de 2
Por lo tanto, la frecuencia máxima es de potencia 2, que es 4
Enfoque: el problema dado se puede resolver encontrando las 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:
- Itere la array arr desde el índice 2 hasta el final y en cada índice:
- Use un ciclo para multiplicar el índice por sí mismo hasta que el valor sea menor que el valor máximo de entero y menor o igual que el elemento presente en ese índice
- Si el poder se vuelve igual al elemento, verifique si está presente en el mapa hash:
- Si el poder no está presente, agréguelo en el mapa hash con valor 1
- De lo contrario, si la energía ya está presente, incremente su frecuencia en 1
- Si el poder se vuelve igual al elemento, verifique si está presente en el mapa hash:
- Use un ciclo para multiplicar el índice por sí mismo hasta que el valor sea menor que el valor máximo de entero y menor o igual que el elemento presente en ese índice
- Si arr[0] = 1, entonces incremente la frecuencia de 0 en el hashmap en 1
- Itere el HashMap y encuentre el valor con la frecuencia máxima:
- Si arr[0] = 1, entonces la frecuencia de todos los valores excepto 0 se incrementa en 1
- Si arr[1] = 1, entonces devuelve maxFreq +1, de lo contrario devuelve maxFreq
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)
{
// Length of the array
int len = arr.size();
// Initialize the hashmap to store
// the frequency of elements
unordered_map<int, int> map;
// Initialize maximum value
// of integer into long
long limit = INT_MAX;
// Iterate the array arr from index 2
for (int i = 2; i < len; i++)
{
// If current element is equal to 1
// then its equal to index power 0
if (arr[i] == 1)
{
// Increment the frequency of 0 by 1
map[0]++;
continue;
}
// Initialize a variable to index
// which is to be multiplied
// by the index
long indPow = i;
// Initialize a variable to
// store the power of the index
int p = 1;
while (indPow <= limit && indPow <= arr[i])
{
// Element is equal to
// a power of its index
if (arr[i] == indPow)
{
// Increment the frequency
// of p by 1
map[p]++;
break;
}
// Increment power
p++;
// Multiply current value with
// index to get the next power
indPow *= i;
}
}
// If arr[0] == 1, then increment
// the frequency of 0 in the hashmap
map[0]++;
// Initialize maxFreq to 0 to calculate
// maximum frequency of powers
int maxFreq = 0;
// Iterate the hashmap
for (auto it = map.begin(); it != map.end(); it++)
{
int power = it->second;
// If arr[0] == 0, then increment the
// frequency of all powers except 0
if (arr[0] == 0 && power != 0)
{
maxFreq = max(maxFreq,
map[power] + 1);
}
else
{
maxFreq = max(maxFreq,
map[power]);
}
}
// Increment the maximum frequency by 1
// If arr[1] is equal to 1
return arr[1] == 1
? maxFreq + 1
: maxFreq;
}
// Driver function
int main()
{
// Initialize an array
vector<int> arr = {0, 1, 1, 9, 1, 25};
// Call the function
// and print the answer
cout << (indPowEqualsEle(arr));
}
// 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)
{
// Length of the array
int len = arr.length;
// Initialize the hashmap to store
// the frequency of elements
Map<Integer, Integer> map
= new HashMap<>();
// Initialize maximum value
// of integer into long
long limit = (long)Integer.MAX_VALUE;
// Iterate the array arr from index 2
for (int i = 2; i < len; i++) {
// If current element is equal to 1
// then its equal to index power 0
if (arr[i] == 1) {
// Increment the frequency of 0 by 1
map.put(0,
map.getOrDefault(0, 0) + 1);
continue;
}
// Initialize a variable to index
// which is to be multiplied
// by the index
long indPow = i;
// Initialize a variable to
// store the power of the index
int p = 1;
while (indPow <= limit
&& indPow <= arr[i]) {
// Element is equal to
// a power of its index
if (arr[i] == indPow) {
// Increment the frequency
// of p by 1
map
.put(p,
map.getOrDefault(p, 0) + 1);
break;
}
// Increment power
p++;
// Multiply current value with
// index to get the next power
indPow *= i;
}
}
// If arr[0] == 1, then increment
// the frequency of 0 in the hashmap
map.put(0, map.getOrDefault(0, 0) + 1);
// Initialize maxFreq to 0 to calculate
// maximum frequency of powers
int maxFreq = 0;
// Iterate the hashmap
for (int power : map.keySet()) {
// If arr[0] == 0, then increment the
// frequency of all powers except 0
if (arr[0] == 0 && power != 0) {
maxFreq
= Math.max(maxFreq,
map.get(power) + 1);
}
else {
maxFreq = Math.max(maxFreq,
map.get(power));
}
}
// Increment the maximum frequency by 1
// If arr[1] is equal to 1
return arr[1] == 1
? maxFreq + 1
: maxFreq;
}
// Driver function
public static void main(String[] args)
{
// Initialize an array
int[] arr = { 0, 1, 1, 9, 1, 25 };
// Call the function
// and print the answer
System.out.println(indPowEqualsEle(arr));
}
}
Python3
# Python 3 code for the above approach from collections import defaultdict import sys # Function to find count of elements which # are a non-negative power of their indices def indPowEqualsEle(arr): # Length of the array length = len(arr) # Initialize the hashmap to store # the frequency of elements map = defaultdict(int) # Initialize maximum value # of integer into long limit = sys.maxsize # Iterate the array arr from index 2 for i in range(2, length): # If current element is equal to 1 # then its equal to index power 0 if (arr[i] == 1): # Increment the frequency of 0 by 1 map[0] += 1 continue # Initialize a variable to index # which is to be multiplied # by the index indPow = i # Initialize a variable to # store the power of the index p = 1 while (indPow <= limit and indPow <= arr[i]): # Element is equal to # a power of its index if (arr[i] == indPow): # Increment the frequency # of p by 1 map[p] += 1 break # Increment power p += 1 # Multiply current value with # index to get the next power indPow *= i # If arr[0] == 1, then increment # the frequency of 0 in the hashmap map[0] += 1 # Initialize maxFreq to 0 to calculate # maximum frequency of powers maxFreq = 0 # Iterate the hashmap for it in range(len(map)): power = map[it] # If arr[0] == 0, then increment the # frequency of all powers except 0 if (arr[0] == 0 and power != 0): maxFreq = max(maxFreq, map[power] + 1) else: maxFreq = max(maxFreq, map[power]) # Increment the maximum frequency by 1 # If arr[1] is equal to 1 if(arr[1] == 1): return maxFreq + 1 return maxFreq # Driver function if __name__ == "__main__": # Initialize an array arr = [0, 1, 1, 9, 1, 25] # Call the function # and print the answer print(indPowEqualsEle(arr)) # This code is contributed by ukasp.
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to find count of elements which
// are a non-negative power of their indices
public static int indPowEqualsEle(int[] arr)
{
// Length of the array
int len = arr.Length;
// Initialize the hashmap to store
// the frequency of elements
Dictionary<int, int> map
= new Dictionary<int, int>();
// Initialize maximum value
// of integer into long
long limit = (long)int.MaxValue;
// Iterate the array arr from index 2
for (int i = 2; i < len; i++) {
// If current element is equal to 1
// then its equal to index power 0
if (arr[i] == 1) {
// Increment the frequency of 0 by 1
if(map.ContainsKey(0))
map[0] = map[0]+1;
else
map.Add(0, 1);
continue;
}
// Initialize a variable to index
// which is to be multiplied
// by the index
long indPow = i;
// Initialize a variable to
// store the power of the index
int p = 1;
while (indPow <= limit
&& indPow <= arr[i]) {
// Element is equal to
// a power of its index
if (arr[i] == indPow) {
// Increment the frequency
// of p by 1
if(map.ContainsKey(p))
map[p] = map[p]+1;
else
map.Add(p, 1);
break;
}
// Increment power
p++;
// Multiply current value with
// index to get the next power
indPow *= i;
}
}
// If arr[0] == 1, then increment
// the frequency of 0 in the hashmap
if(map.ContainsKey(0))
map[0] = map[0]+1;
else
map.Add(0, 1);
// Initialize maxFreq to 0 to calculate
// maximum frequency of powers
int maxFreq = 0;
// Iterate the hashmap
foreach (int power in map.Keys) {
// If arr[0] == 0, then increment the
// frequency of all powers except 0
if (arr[0] == 0 && power != 0) {
maxFreq
= Math.Max(maxFreq,
map[power] + 1);
}
else {
maxFreq = Math.Max(maxFreq,
map[power]);
}
}
// Increment the maximum frequency by 1
// If arr[1] is equal to 1
return arr[1] == 1
? maxFreq + 1
: maxFreq;
}
// Driver function
public static void Main(String[] args)
{
// Initialize an array
int[] arr = { 0, 1, 1, 9, 1, 25 };
// Call the function
// and print the answer
Console.WriteLine(indPowEqualsEle(arr));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript code for the above approach
// Function to find count of elements which
// are a non-negative power of their indices
function indPowEqualsEle(arr) {
// Length of the array
let len = arr.length;
// Initialize the hashmap to store
// the frequency of elements
let map = new Map();
// Initialize maximum value
// of integer into long
let limit = Number.MAX_SAFE_INTEGER;
// Iterate the array arr from index 2
for (let i = 2; i < len; i++) {
// If current element is equal to 1
// then its equal to index power 0
if (arr[i] == 1) {
// Increment the frequency of 0 by 1
if (map.has(0)) {
map.set(0, map.get(0) + 1)
} else {
map.set(0, 1)
}
continue;
}
// Initialize a variable to index
// which is to be multiplied
// by the index
let indPow = i;
// Initialize a variable to
// store the power of the index
let p = 1;
while (indPow <= limit && indPow <= arr[i]) {
// Element is equal to
// a power of its index
if (arr[i] == indPow) {
// Increment the frequency
// of p by 1
if (map.has(p)) {
map.set(p, map.get(p) + 1)
} else {
map.set(p, 1)
}
break;
}
// Increment power
p++;
// Multiply current value with
// index to get the next power
indPow *= i;
}
}
// If arr[0] == 1, then increment
// the frequency of 0 in the hashmap
if (map.has(0)) {
map.set(0, map.get(0) + 1)
} else {
map.set(0, 1)
}
// Initialize maxFreq to 0 to calculate
// maximum frequency of powers
let maxFreq = 0;
// Iterate the hashmap
for (let power of map.keys()) {
// If arr[0] == 0, then increment the
// frequency of all powers except 0
if (arr[0] == 0 && power != 0) {
maxFreq = Math.max(maxFreq,
map.get(power) + 1);
}
else {
maxFreq = Math.max(maxFreq,
map.get(power));
}
}
// Increment the maximum frequency by 1
// If arr[1] is equal to 1
return arr[1] == 1
? maxFreq + 1
: maxFreq;
}
// Driver function
// Initialize an array
let arr = [0, 1, 1, 9, 1, 25];
// Call the function
// and print the answer
document.write((indPowEqualsEle(arr)))
// This code is contributed by gfgking.
</script>
Producción
4
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aditya1762002 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA