Given Array of size n and a number k, find all elements that appear more than n/k times

Last Updated : 18 Apr, 2023

Given an array of size n and an integer k, find all elements in the array that appear more than n/k times.

Examples:

Input: arr[] = {3, 1, 2, 2, 1, 2, 3, 3}, k = 4
Output: {2, 3}
Explanation: Here n/k is 8/4 = 2, therefore 2 appears 3 times in the array that is greater than 2 and 3 appears 3 times in the array that is greater than 2

Input: arr[] = {9, 8, 7, 9, 2, 9, 7}, k = 3
Output: {9}
Explanation: Here n/k is 7/3 = 2, therefore 9 appears 3 times in the array that is greater than 2.

Find all elements that appear more than n/k times using Hashing:

The idea is to pick all elements one by one. For every picked element, count its occurrences by traversing the array, if count becomes more than n/k, then print the element.

Follow the steps below to solve the problem:

First, make a frequency map of all the elements in the array
Then traverse the map and check the frequency of every element
If the frequency is greater than n/k then print the element.

Below is the implementation of the above approach:

C++

// C++ code to find elements whose
// frequency is more than n/k
#include <bits/stdc++.h>
using namespace std;
 
void morethanNbyK(int arr[], int n, int k)
{
    int x = n / k;
 
    // unordered_map initialization
    unordered_map<int, int> freq;
 
    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
    }
 
    // Traversing the map
    for (auto i : freq) {
 
        // Checking if value of a key-value pair
        // is greater than x (where x=n/k)
        if (i.second > x) {
 
            // Print the key of whose value
            // is greater than x
            cout << i.first << endl;
        }
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4;
 
    morethanNbyK(arr, n, k);
 
    return 0;
}
 
// This code is contributed by chayandas018

Java

// Java Code to find elements whose
// frequency is more than n/k
import java.util.*;
 
public class Main
 
{
    public static void morethanNdK(int a[], int n, int k)
    {
        int x = n / k;
 
        // Hash map initialization
        HashMap<Integer, Integer> y = new HashMap<>();
 
        // count the frequency of each element.
        for (int i = 0; i < n; i++) {
            // is element doesn't exist in hash table
            if (!y.containsKey(a[i]))
                y.put(a[i], 1);
 
            // if element does exist in the hash table
            else {
                int count = y.get(a[i]);
                y.put(a[i], count + 1);
            }
        }
 
        // iterate over each element in the hash table
        // and check their frequency, if it is more than
        // n/k, print it.
        for (Map.Entry m : y.entrySet()) {
            Integer temp = (Integer)m.getValue();
            if (temp > x)
                System.out.println(m.getKey());
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int a[] = new int[] { 1, 1, 2, 2, 3, 5, 4,
                              2, 2, 3, 1, 1, 1 };
        int n = 12;
        int k = 4;
        morethanNdK(a, n, k);
    }
}

Python3

# Python3 code to find elements whose
# frequency is more than n/k
 
 
def morethanNbyK(arr, n, k):
    x = n // k
 
    # unordered_map initialization
    freq = {}
 
    for i in range(n):
        if arr[i] in freq:
            freq[arr[i]] += 1
        else:
            freq[arr[i]] = 1
 
    # Traversing the map
    for i in freq:
 
        # Checking if value of a key-value pair
        # is greater than x (where x=n/k)
        if (freq[i] > x):
 
            # Print the key of whose value
            # is greater than x
            print(i)
 
 
# Driver code
if __name__ == '__main__':
    arr = [1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1]
    n = len(arr)
    k = 4
     
    morethanNbyK(arr, n, k)
 
# This code is contributed by mohit kumar 29

C#

// C# code to find elements whose
// frequency is more than n/k
using System;
using System.Collections.Generic;
 
class GFG {
 
    public static void morethanNdK(int[] a, int n, int k)
    {
        int x = n / k;
 
        // Hash map initialization
        Dictionary<int, int> y = new Dictionary<int, int>();
 
        // Count the frequency of each element.
        for (int i = 0; i < n; i++) {
 
            // Is element doesn't exist in hash table
            if (!y.ContainsKey(a[i]))
                y.Add(a[i], 1);
 
            // If element does exist in the hash table
            else {
                int count = y[a[i]];
                y[a[i]] = count + 1;
            }
        }
 
        // Iterate over each element in the hash table
        // and check their frequency, if it is more than
        // n/k, print it.
        foreach(KeyValuePair<int, int> m in y)
        {
            int temp = (int)m.Value;
            if (temp > x)
                Console.WriteLine(m.Key);
        }
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] a = new int[] { 1, 1, 2, 2, 3, 5, 4,
                              2, 2, 3, 1, 1, 1 };
        int n = 12;
        int k = 4;
 
        morethanNdK(a, n, k);
    }
}
 
// This code is contributed by Princi Singh

Javascript

<script>
// Javascript Code to find elements whose
// frequency is more than n/k
     
    function morethanNdK(a,n,k)
    {
        let x = n / k;
        // Hash map initialization
        let y=new Map();
        // count the frequency of each element.
        for (let i = 0; i < n; i++)
        {
            // is element doesn't exist in hash table
            if (!y.has(a[i]))
                y.set(a[i], 1);
            
            
            // if element does exist in the hash table
            else
            {
                let count = y.get(a[i]);
                y.set(a[i], count + 1);
            }
        }
  
        // iterate over each element in the hash table
        // and check their frequency, if it is more than
        // n/k, print it.
        for (let [key, value] of y.entries())
        {
            let temp = value;
            if (temp > x)
                document.write(key+"<br>");
        }
    }
     
    let a=[1, 1, 2, 2, 3, 5, 4,
                              2, 2, 3, 1, 1, 1];
    let n = 12;
    let k = 4;
    morethanNdK(a, n, k);
     
    // This code is contributed by unknown2108
</script>

Output

2
1

Time Complexity: O(N), Traversing the array of size N.
Auxiliary Space: O(N), Space occupied by the hashmap

Find all elements that appear more than n/k times using Moore’s Voting Algorithm:

The idea is to apply Moore’s Voting algorithm, as there can be at max k – 1 elements present in the array which appears more than n/k times so their will be k – 1 candidates. When we encounter an element which is one of our candidates then increment the count else decrement the count.

Illustration:

Consider k = 4, n = 9
Given array: 3 1 2 2 2 1 4 3 3

i = 0
temp[] has one element {3} with count 1

i = 1
temp[] has two elements {3, 1} with counts 1 and 1 respectively

i = 2
temp[] has three elements, {3, 1, 2} with counts as 1, 1 and 1 respectively.

i = 3
temp[] has three elements, {3, 1, 2} with counts as 1, 1 and 2 respectively.

i = 4
temp[] has three elements, {3, 1, 2} with counts as 1, 1 and 3 respectively.

i = 5
temp[] has three elements, {3, 1, 2 with counts as 1, 2 and 3 respectively.

i = 6
temp[] has two elements, {1, 2} with counts as 1 and 2 respectively.

i = 7
temp[] has three elements, {3, 1, 2} with counts as 1, 1 and 2 respectively.

i = 8
temp[] has three elements, {3, 1, 2} with counts as 2, 1 and 2 respectively.

Follow the steps below to solve the problem:

Create a temporary array of size (k – 1) to store elements and their counts (The output elements are going to be among these k-1 elements).
Traverse through the input array and update temp[] (add/remove an element or increase/decrease count) for every traversed element. The array temp[] stores potential (k-1) candidates at every step.
Iterate through final (k-1) potential candidates (stored in temp[]). or every element, check if it actually has counted of more than n/k.

Below is the implementation of the above approach.

C++

// A C++ program to print elements with count more than n/k
#include <iostream>
using namespace std;
 
// A structure to store an element and its current count
struct eleCount {
    int e; // Element
    int c; // Count
};
 
// Prints elements with more
// than n/k occurrences in arr[]
// of size n. If there are no
// such elements, then it prints
// nothing.
void moreThanNdK(int arr[], int n, int k)
{
    // k must be greater than
    // 1 to get some output
    if (k < 2)
        return;
 
    /* Step 1: Create a temporary
       array (contains element
       and count) of size k-1.
       Initialize count of all
       elements as 0 */
    struct eleCount temp[k - 1];
    for (int i = 0; i < k - 1; i++)
        temp[i].c = 0;
 
    /* Step 2: Process all
      elements of input array */
    for (int i = 0; i < n; i++) {
        int j;
 
        /* If arr[i] is already present in
           the element count array,
           then increment its count
         */
        for (j = 0; j < k - 1; j++) {
            if (temp[j].e == arr[i]) {
                temp[j].c += 1;
                break;
            }
        }
 
        /* If arr[i] is not present in temp[] */
        if (j == k - 1) {
            int l;
 
            /* If there is position available
              in temp[], then place arr[i] in
              the first available position and
              set count as 1*/
            for (l = 0; l < k - 1; l++) {
                if (temp[l].c == 0) {
                    temp[l].e = arr[i];
                    temp[l].c = 1;
                    break;
                }
            }
 
            /* If all the position in the
               temp[] are filled, then decrease
               count of every element by 1 */
            if (l == k - 1)
                for (l = 0; l < k - 1; l++)
                    temp[l].c -= 1;
        }
    }
 
    /*Step 3: Check actual counts of
     * potential candidates in temp[]*/
    for (int i = 0; i < k - 1; i++) {
        // Calculate actual count of elements
        int ac = 0; // actual count
        for (int j = 0; j < n; j++)
            if (arr[j] == temp[i].e)
                ac++;
 
        // If actual count is more than n/k,
        // then print it
        if (ac > n / k)
            cout << "Number:" << temp[i].e
                 << " Count:" << ac << endl;
    }
}
 
/* Driver code */
int main()
{
 
    int arr1[] = { 4, 5, 6, 7, 8, 4, 4 };
    int size = sizeof(arr1) / sizeof(arr1[0]);
    int k = 3;
    moreThanNdK(arr1, size, k);
 
    return 0;
}

Java

// A Java program to print elements with count more than n/k
import java.util.*;
 
class GFG {
 
    // A structure to store an element and its current count
    static class eleCount {
        int e; // Element
        int c; // Count
    };
 
    // Prints elements with more
    // than n/k occurrences in arr[]
    // of size n. If there are no
    // such elements, then it prints
    // nothing.
    static void moreThanNdK(int arr[], int n, int k)
    {
        // k must be greater than
        // 1 to get some output
        if (k < 2)
            return;
 
        /* Step 1: Create a temporary
           array (contains element
           and count) of size k-1.
           Initialize count of all
           elements as 0 */
        eleCount[] temp = new eleCount[k - 1];
        for (int i = 0; i < k - 1; i++)
            temp[i] = new eleCount();
        for (int i = 0; i < k - 1; i++) {
            temp[i].c = 0;
        }
 
        /* Step 2: Process all
          elements of input array */
        for (int i = 0; i < n; i++) {
            int j;
 
            /* If arr[i] is already present in
               the element count array,
               then increment its count
             */
            for (j = 0; j < k - 1; j++) {
                if (temp[j].e == arr[i]) {
                    temp[j].c += 1;
                    break;
                }
            }
 
            /* If arr[i] is not present in temp[] */
            if (j == k - 1) {
                int l;
 
                /* If there is position available
                  in temp[], then place arr[i] in
                  the first available position and
                  set count as 1*/
                for (l = 0; l < k - 1; l++) {
                    if (temp[l].c == 0) {
                        temp[l].e = arr[i];
                        temp[l].c = 1;
                        break;
                    }
                }
 
                /* If all the position in the
                   temp[] are filled, then decrease
                   count of every element by 1 */
                if (l == k - 1)
                    for (l = 0; l < k - 1; l++)
                        temp[l].c -= 1;
            }
        }
 
        /*Step 3: Check actual counts of
         * potential candidates in temp[]*/
        for (int i = 0; i < k - 1; i++) {
 
            // Calculate actual count of elements
            int ac = 0; // actual count
            for (int j = 0; j < n; j++)
                if (arr[j] == temp[i].e)
                    ac++;
 
            // If actual count is more than n/k,
            // then print it
            if (ac > n / k)
                System.out.print("Number:" + temp[i].e
                                 + " Count:" + ac + "\n");
        }
    }
 
    /* Driver code */
    public static void main(String[] args)
    {
        int arr1[] = { 4, 5, 6, 7, 8, 4, 4 };
        int size = arr1.length;
        int k = 3;
        moreThanNdK(arr1, size, k);
    }
}
 
// This code contributed by Princi Singh .

Python3

# A Python3 program to print elements with
# count more than n/k
 
# Prints elements with more than n/k
# occurrences in arrof size n. If
# there are no such elements, then
# it prints nothing.
 
 
def moreThanNdK(arr, n, k):
 
    # k must be greater than 1
    # to get some output
    if (k < 2):
        return
 
    # Step 1: Create a temporary array
    # (contains element and count) of
    # size k-1. Initialize count of all
    # elements as 0
    temp = [[0 for i in range(2)]
            for i in range(k)]
 
    for i in range(k - 1):
        temp[i][0] = 0
 
    # Step 2: Process all elements
    # of input array
    for i in range(n):
        j = 0
 
        # If arr[i] is already present in
        # the element count array, then
        # increment its count
        while j < k - 1:
            if (temp[j][1] == arr[i]):
                temp[j][0] += 1
                break
 
            j += 1
 
        # If arr[i] is not present in temp
        if (j == k - 1):
            l = 0
 
            # If there is position available
            # in temp[], then place arr[i]
            # in the first available position
            # and set count as 1*/
            while l < k - 1:
                if (temp[l][0] == 0):
                    temp[l][1] = arr[i]
                    temp[l][0] = 1
                    break
 
                l += 1
 
            # If all the position in the
            # tempare filled, then decrease
            # count of every element by 1
            if (l == k - 1):
                while l < k:
                    temp[l][0] -= 1
                    l += 1
 
    # Step 3: Check actual counts
    # of potential candidates in temp[]
    for i in range(k - 1):
 
        # Calculate actual count of elements
        ac = 0  # Actual count
        for j in range(n):
            if (arr[j] == temp[i][1]):
                ac += 1
 
        # If actual count is more
        # than n/k, then print
        if (ac > n // k):
            print("Number:",
                  temp[i][1],
                  " Count:", ac)
 
 
# Driver code
if __name__ == '__main__':
 
    arr1 = [4, 5, 6, 7, 8, 4, 4]
    size = len(arr1)
    k = 3
    moreThanNdK(arr1, size, k)
# This code is contributed by mohit kumar 29

C#

// A C# program to print elements
// with count more than n/k
using System;
class GFG {
 
    // A structure to store an element
    // and its current count
    public class eleCount {
        public int e; // Element
        public int c; // Count
    };
 
    // Prints elements with more
    // than n/k occurrences in []arr
    // of size n. If there are no
    // such elements, then it prints
    // nothing.
    static void moreThanNdK(int[] arr, int n, int k)
    {
 
        // k must be greater than
        // 1 to get some output
        if (k < 2)
            return;
 
        /* Step 1: Create a temporary
           array (contains element
           and count) of size k-1.
           Initialize count of all
           elements as 0 */
        eleCount[] temp = new eleCount[k - 1];
        for (int i = 0; i < k - 1; i++)
            temp[i] = new eleCount();
        for (int i = 0; i < k - 1; i++) {
            temp[i].c = 0;
        }
 
        /* Step 2: Process all
          elements of input array */
        for (int i = 0; i < n; i++) {
            int j;
 
            /* If arr[i] is already present in
               the element count array,
               then increment its count
             */
            for (j = 0; j < k - 1; j++) {
                if (temp[j].e == arr[i]) {
                    temp[j].c += 1;
                    break;
                }
            }
 
            /* If arr[i] is not present in []temp */
            if (j == k - 1) {
                int l;
 
                /* If there is position available
                  in []temp, then place arr[i] in
                  the first available position and
                  set count as 1*/
                for (l = 0; l < k - 1; l++) {
                    if (temp[l].c == 0) {
                        temp[l].e = arr[i];
                        temp[l].c = 1;
                        break;
                    }
                }
 
                /* If all the position in the
                   []temp are filled, then decrease
                   count of every element by 1 */
                if (l == k - 1)
                    for (l = 0; l < k - 1; l++)
                        temp[l].c -= 1;
            }
        }
 
        /*Step 3: Check actual counts of
         * potential candidates in []temp*/
        for (int i = 0; i < k - 1; i++) {
 
            // Calculate actual count of elements
            int ac = 0; // actual count
            for (int j = 0; j < n; j++)
                if (arr[j] == temp[i].e)
                    ac++;
 
            // If actual count is more than n/k,
            // then print it
            if (ac > n / k)
                Console.Write("Number:" + temp[i].e
                              + " Count:" + ac + "\n");
        }
    }
 
    /* Driver code */
    public static void Main(String[] args)
    {
        int[] arr1 = { 4, 5, 6, 7, 8, 4, 4 };
        int size = arr1.Length;
        int k = 3;
        moreThanNdK(arr1, size, k);
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// A JavaScript program to print elements with
// count more than n/k
 
// Prints elements with more than n/k
// occurrences in arrof size n. If
// there are no such elements, then
// it prints nothing.
function moreThanNdK(arr, n, k){
 
    // k must be greater than 1
    // to get some output
    if (k < 2)
        return;
 
    // Step 1: Create a temporary array
    // (contains element and count) of
    // size k-1. Initialize count of all
    // elements as 0
    let temp = new Array(k-1);
 
    for(let i = 0; i < k - 1; i++){
        temp[i] = new Array(2);
        temp[i][0] = 0;
    }
 
    // Step 2: Process all elements
    // of input array
    for(let i = 0; i < n; i++){
        let j;
 
        // If arr[i] is already present in
        // the element count array, then
        // increment its count
        for (j = 0; j < k - 1; j++)
        {
            if (temp[j][1] == arr[i])
            {
                temp[j][0] += 1;
                break;
            }
        }
 
        // If arr[i] is not present in temp
        if (j == k - 1){
            let l;
 
            // If there is position available
            // in temp[], then place arr[i]
            // in the first available position
            // and set count as 1*/
            for (l = 0; l < k - 1; l++)
            {
                if (temp[l][0] == 0)
                {
                    temp[l][1] = arr[i];
                    temp[l][0] = 1;
                    break;
                }
            }
 
            // If all the position in the
            // tempare filled, then decrease
            // count of every element by 1
            if (l == k - 1)
                for (l = 0; l < k-1; l++)
                    temp[l][0] -= 1;
        }
    }
 
    // Step 3: Check actual counts
    // of potential candidates in temp[]
    for(let i = 0; i < k - 1; i++){
 
        // Calculate actual count of elements
        let ac = 0 // Actual count
        for(let j = 0; j < n; j++){
            if (arr[j] == temp[i][1])
                ac++;
        }
 
        // If actual count is more
        // than n/k, then print
        if (ac > Math.floor(n/k))
            document.write("Number: " + temp[i][1] + 
            " Count: " + ac,"</br>")
     
    }
}
 
// Driver code
document.write("First Test","</br>")
let arr1 = [4, 5, 6, 7, 8, 4, 4]
let size = arr1.length
let k = 3
moreThanNdK(arr1, size, k)
 
document.write("Second Test","</br>")
let arr2 = [4, 2, 2, 7]
size = arr2.length
k = 3
moreThanNdK(arr2, size, k)
 
document.write("Third Test","</br>")
let arr3 = [2, 7, 2]
size = arr3.length
k = 2
moreThanNdK(arr3, size, k)
 
document.write("Fourth Test","</br>")
let arr4 = [2, 3, 3, 2]
size = arr4.length
k = 3
moreThanNdK(arr4, size, k)
 
// This code is contributed by shinjanpatra
 
</script>

Output

Number:4 Count:3

Time Complexity: O(N * K), Checking for each element of the array(size N) in the candidate array of size K
Auxiliary Space: O(K), Space required to store the candidates.

Find all elements that appear more than n/k times using Built-in Python functions:

This approach is same the first approach but here in python there is a counter() that calculates the frequency array.

Count the frequencies of every element using Counter() function.
Traverse the frequency array and print all the elements which occur at more than n/k times.

Below is the implementation of the above approach:

Python3

# Python3 implementation
from collections import Counter
 
# Function to find the number of array
# elements with frequency more than n/k times
def printElements(arr, n, k):
 
    # Calculating n/k
    x = n//k
 
    # Counting frequency of every 
    # element using Counter
    mp = Counter(arr)
     
    # Traverse the map and print all
    # the elements with occurrence 
    # more than n/k times
    for it in mp:
        if mp[it] > x:
            print(it)
 
 
# Driver code
if __name__ == '__main__':
    arr = [1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1]
    n = len(arr)
    k = 4
     
    printElements(arr, n, k)
 
# This code is contributed by vikkycirus

Java

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
 
class GFG {
    
    public static void printElements(int[] arr, int n, int k) {
        // Calculating n/k
        int x = n / k;
 
        // Counting frequency of every element using a HashMap
        HashMap<Integer, Integer> mp = new HashMap<>();
        for (int i : arr) {
            if (mp.containsKey(i)) {
                mp.put(i, mp.get(i) + 1);
            } else {
                mp.put(i, 1);
            }
        }
         
        // Traverse the map and print all the elements with occurrence more than n/k times
        for (int key : mp.keySet()) {
            if (mp.get(key) > x) {
                System.out.println(key);
            }
        }
    }
 
    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1};
        int n = arr.length;
        int k = 4;
        printElements(arr, n, k);
    }
}
// This code is contributed by Shivam Tiwari

C++

#include <iostream>
#include <unordered_map>
using namespace std;
 
// Function to find the number of array
// elements with frequency more than n/k times
void printElements(int arr[], int n, int k)
{
    // Calculating n/k
    int x = n/k;
 
    // Counting frequency of every element
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++)
        mp[arr[i]]++;
 
    // Traverse the map and print all
    // the elements with occurrence
    // more than n/k times
    for (auto it : mp)
        if (it.second > x)
            cout << it.first << endl;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1 };
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 4;
 
    printElements(arr, n, k);
 
    return 0;
}
 
// This code is contributed by Shivam Tiwari

Javascript

// function to find the number of array
// elements with frequency more than n/k times
function printElements(arr, n, k){
    // calculating n/k
    let x = parseInt(n/k);
 
 
    // counting the frequency of every 
    // element using counter
    let mp = new Map();
    for(let ele of arr){
        if(ele in mp){
            mp[ele] += 1;
        }
        else{
            mp[ele] = 1;
        }
    }
 
    // Traverse the map and print all 
    // the elements with occurrence 
    // more than n/k times 
    for(let it in mp){
        if(mp[it] > x){
            console.log(it);
        }
    }
}
 
// Driver code
let arr = [ 1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1 ];
let n = arr.length;
let k = 4;
printElements(arr, n, k);
 
// This code is contributed by Prince Kumar

C#

using System;
using System.Collections.Generic;
 
class GFG
{
    static void Main()
    {
        int[] arr = { 1, 1, 2, 2, 3, 5, 4, 2, 2, 3, 1, 1, 1 };
        int n = arr.Length;
        int k = 4;
 
        PrintElements(arr, n, k);
    }
 
    static void PrintElements(int[] arr, int n, int k)
    {
        // Calculating n/k
        int x = n / k;
 
        // Counting frequency of every element
        Dictionary<int, int> mp = new Dictionary<int, int>();
        for (int i = 0; i < n; i++)
        {
            // If the element is already in the dictionary, increment its count by 1
            if (mp.ContainsKey(arr[i]))
            {
                mp[arr[i]]++;
            }
            // If the element is not in the dictionary, add it with a count of 1
            else
            {
                mp[arr[i]] = 1;
            }
        }
 
        // Traverse the dictionary and print all the elements with occurrence more than n/k times
        foreach (KeyValuePair<int, int> item in mp)
        {
            if (item.Value > x)
            {
                Console.WriteLine(item.Key);
            }
        }
    }
}
// This code is contributed by Shivam Tiwari

Output

1
2

Time Complexity: O(N), Traversing over the array to store the frequency
Auxiliary Space: O(N), Space used to store the frequency

GeeksforGeeks

Improve

Previous Article

Find the maximum element in an array which is first increasing and then decreasing

Find all triplets with zero sum

Similar Reads

Remove elements from the array which appear more than k times

Given an array of integers, remove all the occurrences of those elements which appear strictly more than k times in the array.Examples: Input : arr[] = {1, 2, 2, 3, 2, 3, 4} k = 2Output : 1 3 3 4Input : arr[] = {2, 5, 5, 7} k = 1Output : 2 7Approach: Take a hash map, which will store the frequency of all the elements in the array.Now, traverse once

Count possible N-digit numbers such that each digit does not appear more than given number of times consecutively

Given an integer N and an array maxDigit[], the task is to count all the distinct N-digit numbers such that digit i does not appear more than maxDigit[i] times. Since the count can be very large, print it modulo 109 + 7. Examples: Input: N = 2, maxDigit[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}Output: 90Explanation:Any digit can't appear more than once co

Remove characters that appear more than k times

Given a string of lowercase letters, reduce it by removing the characters which appear more than k times in the string. Examples: Input: str = "geeksforgeeks" k = 2 Output: for Input: str = "geeksforgeeks" k = 3 Output: gksforgks Approach : Create a hash table of 26 indexes, where the 0th index represents 'a' and 1th index represents 'b' and so on.

Array elements that appear more than once

Given an integer array, print all repeating elements (Elements that appear more than once) in the array. The output should contain elements according to their first occurrences. Examples: Input: arr[] = {12, 10, 9, 45, 2, 10, 10, 45}Output: 10 45 Input: arr[] = {1, 2, 3, 4, 2, 5}Output:2 Input: arr[] = {1, 1, 1, 1, 1}Output: 1 Recommended: Please s

Remove elements that appear strictly less than k times

Given an array of integers, remove all the elements which appear strictly less than k times. Examples: Input : arr[] = {1, 2, 2, 3, 2, 3, 4} k = 2 Output : 2 2 3 2 3 Explanation : {1, 4} appears less than 2 times. Approach : Take a hash map, which will store the frequency of all the elements in the array.Now, traverse once again.Remove the elements

Find all array elements occurring more than ⌊N/3⌋ times

Given an array arr[] consisting of N integers, the task is to find all the array elements which occurs more than floor (n/3) times. Examples: Input: arr[] = {5, 3, 5}Output: 5Explanation:The frequency of 5 is 2, which is more than N/3(3/3 = 1). Input: arr[] = {7, 7, 7, 3, 4, 4, 4, 5}Output: 4 7Explanation:The frequency of 7 and 4 in the array is 3,

Length of longest subarray in which elements greater than K are more than elements not greater than K

Given an array arr[] of length N. The task is to find the length of the longest subarray in which elements greater than a given number K are more than elements not greater than K.Examples: Input : N = 5, K = 2, arr[]={ 1, 2, 3, 4, 1 } Output : 3 The subarray [2, 3, 4] or [3, 4, 1] satisfy the given condition, and there is no subarray of length 4 or

Print all array elements appearing more than N / K times

Given an array arr[] of size N and an integer K, the task is to find all the array elements that appear more than (N / K) times. Examples: Input: arr[] = { 1, 2, 6, 6, 6, 6, 6, 10 }, K = 4Output: 6Explanation: The frequency of 6 in the array is greater than N / K(= 2). Therefore, the required output is 6. Input: arr[] = { 3, 4, 4, 5, 5, 5, 5 }, K =

For each A[i] find smallest subset with all elements less than A[i] sum more than B[i]

Given two arrays A[] and B[] of N integers, the task is to find for each element A[i], the size of the smallest subset S of indices, such that : Each value corresponding to the indices in subset S is strictly less than A[i].Sum of elements corresponding to the indices in B is strictly greater than B[i]. Examples: Input: N = 5, A = {3, 2, 100, 4, 5}

Sum of all numbers formed having 4 atmost X times, 5 atmost Y times and 6 atmost Z times

Given three integers X, Y and Z, the task is to find the sum of all the numbers formed having 4 at most X times, 5 at most Y times, and 6 at most Z times, under mod 10^9+7.Examples: Input: X = 1, Y = 1, Z = 1 Output: 3675 Explanation: 4 + 5 + 6 + 45 + 54 + 56 + 65 + 46 + 64 + 456 + 465 + 546 + 564 + 645 + 654 = 3675 Input: X = 4, Y = 5, Z = 6 Outpu

Article Tags :

Practice Tags :