Dado un arreglo arr[] que consta de N enteros y un entero positivo K , la tarea es encontrar los elementos del arreglo que tengan frecuencias en la potencia de K , es decir, K 1 , K 2 , K 3 , etc.
Ejemplos:
Entrada: arr[] = {1, 3, 2, 1, 2, 2, 2, 3, 3, 4}, K = 2
Salida: 1 2
Explicación:
La frecuencia de 1 es 2, que se puede representar como la potencia de K( = 2), es decir, 2 1 .
La frecuencia de 2 es 4, que se puede representar como la potencia de K( = 2), es decir, 2 2 .Entrada: arr[] = {6, 1, 3, 1, 2, 2, 1}, K = 2
Salida: 2 3 6
Enfoque ingenuo: el enfoque más simple es contar las frecuencias de cada elemento de la array y, si la frecuencia de cualquier elemento es una potencia perfecta de K , imprimir ese elemento. De lo contrario, busque el siguiente elemento.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando Hashing para almacenar la frecuencia de los elementos de los arreglos en un HashMap y luego verificar las condiciones requeridas. Siga los pasos a continuación para resolver el problema dado:
- Recorra la array dada arr[] y almacene la frecuencia de cada elemento de la array en un Map , digamos M .
- Ahora, recorra el mapa y realice los siguientes pasos:
- Almacene la frecuencia de cada valor en el mapa en una variable, digamos F .
- Si el valor de (log F)/(log K) y K (log F)/(log K) son iguales, entonces el elemento actual tiene la frecuencia como la potencia perfecta de K . Por lo tanto, imprima el elemento actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the array elements
// whose frequency is a power of K
void countFrequency(int arr[], int N,
int K)
{
// Stores the frequency of each
// array elements
unordered_map<int, int> freq;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update frequency of
// array elements
freq[arr[i]]++;
}
// Traverse the map freq
for (auto i : freq) {
// Calculate the log value of the
// current frequency with base K
int lg = log(i.second) / log(K);
// Find the power of K of log value
int a = pow(K, lg);
// If the values are equal
if (a == i.second) {
// Print the current element
cout << i.first << " ";
}
}
}
// Driver Code
int main()
{
int arr[] = { 1, 4, 4, 2,
1, 2, 3, 2, 2 };
int K = 2;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
countFrequency(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to find the array elements
// whose frequency is a power of K
static void countFrequency(int arr[], int N, int K)
{
// Stores the frequency of each
// array elements
HashMap<Integer, Integer> freq = new HashMap<>();
// Traverse the array
for (int i = 0; i < N; i++) {
// Update frequency of
// array elements
freq.put(arr[i],
freq.getOrDefault(arr[i], 0) + 1);
}
// Traverse the map freq
for (int key : freq.keySet()) {
// Calculate the log value of the
// current frequency with base K
int lg = (int)(Math.log(freq.get(key))
/ Math.log(K));
// Find the power of K of log value
int a = (int)(Math.pow(K, lg));
// If the values are equal
if (a == freq.get(key)) {
// Print the current element
System.out.print(key + " ");
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 4, 4, 2, 1, 2, 3, 2, 2 };
int K = 2;
int N = arr.length;
// Function Call
countFrequency(arr, N, K);
}
}
Python3
# Python3 program for the above approach
# Function to find the array elements
from math import log
def countFrequency(arr, N, K):
# Stores the frequency of each
# array elements
freq = {}
# Traverse the array
for i in range(N):
# Update frequency of
# array elements
if (arr[i] in freq):
freq[arr[i]] += 1
else:
freq[arr[i]] = 1
# Traverse the map freq
for key,value in freq.items():
# Calculate the log value of the
# current frequency with base K
lg = log(value) // log(K)
# Find the power of K of log value
a = pow(K, lg)
# If the values are equal
if (a == value):
# Print the current element
print(key, end = " ")
# Driver Code
if __name__ == '__main__':
arr = [1, 4, 4, 2, 1, 2, 3, 2, 2]
K = 2
N = len(arr)
# Function Call
countFrequency(arr, N, K)
# This code is contributed by bgangwar59.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the array elements
// whose frequency is a power of K
static void countFrequency(int []arr, int N,
int K)
{
// Stores the frequency of each
// array elements
Dictionary<int,
int> freq = new Dictionary<int,
int>();
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update frequency of
// array elements
if (freq.ContainsKey(arr[i]))
freq[arr[i]] += 1;
else
freq[arr[i]] = 1;
}
// Traverse the map freq
foreach (KeyValuePair<int, int> entry in freq)
{
int temp = entry.Key;
// Calculate the log value of the
// current frequency with base K
int lg = (int)(Math.Log(entry.Value) /
Math.Log(K));
// Find the power of K of log value
int a = (int)Math.Pow(K, lg);
// If the values are equal
if (a == entry.Value)
{
// Print the current element
Console.Write(entry.Key + " ");
}
}
}
// Driver Code
public static void Main()
{
int []arr = { 1, 4, 4, 2,
1, 2, 3, 2, 2 };
int K = 2;
int N = arr.Length;
// Function Call
countFrequency(arr, N, K);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program for the above approach
// Function to find the array elements
// whose frequency is a power of K
function countFrequency(arr, N, K)
{
// Stores the frequency of each
// array elements
let freq = new Map();
key = [3, 2, 1, 4]
// Traverse the array
for(let i = 0; i < N; i++)
{
// Update frequency of
// array elements
if (freq.has(arr[i]))
freq.set(arr[i], freq.get(arr[i]) + 1);
else
freq.set(arr[i], 1);
}
let i = 0;
freq.forEach((values,keys)=>{
let temp = keys;
// Calculate the log value of the
// current frequency with base K
let lg = parseInt(Math.log(values) /
Math.log(K), 10);
// Find the power of K of log value
let a = parseInt(Math.pow(K, lg), 10);
// If the values are equal
if (a == values)
{
// Print the current element
document.write(key[i] + " ");
i++;
}
})
}
let arr = [ 1, 4, 4, 2,
1, 2, 3, 2, 2 ];
let K = 2;
let N = arr.length;
// Function Call
countFrequency(arr, N, K);
// This code is contributed by divyeshrabadiya07.
</script>
3 2 1 4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por subhammahato348 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA