Imprima todos los elementos de la array que tengan frecuencias iguales a las potencias de K en orden ascendente

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 ¹ , K ² , K ³ , 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 ¹ .
La frecuencia de 2 es 4, que se puede representar como la potencia de K( = 2), es decir, 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 ² )
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++ 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 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 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# 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

<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)