Table of Contents

## Problem Statement

In the “Elements Appear more than N/K times in Array” problem we have given an integer array of size n. Find the elements which appear more than n/k times. Where k is the input value.

## Input Format

The first and only one line containing two integers N and K.

Second-line containing N space-separated integers.

## Output Format

The first and only one line containing all those integers with space-separated which are present in the array more than n/k times.

## Constraints

- 1<=N,K<=10^5
- -10^9<=a[i]<=10^9

## Example

7 6 1 3 4 7 4 7 5

4 7

**Explanation:** Size of the array (n) = 7, n/k = 1. Therefore, we need to find elements that are coming more than 1 time.

Therefore, output: [4, 7].

10 5 1 1 1 2 2 3 3 4 4 5

1

**Explanation:** Size of the array (n) =10, n/k = 2. Therefore, we need to find elements that are coming more than 2 times.

Therefore, output: [1].

## Algorithm

- Traverse the whole array element by element.
- If the current element is not present in the map then add it to the map with the value 1.
- Else find the current freq of this element and add it into the map with the value freq+1.
- Traverse the whole map and check the value of each key. If the key is greater than n/k then print the key.
- Otherwise, move to the next element.

## Implementation

### C++ Program for Elements Appear more than N/K times in Array

#include <bits/stdc++.h> using namespace std; int main() { int n,k; cin>>n>>k; int a[n]; for(int i=0;i<n;i++) { cin>>a[i]; } int req = n/k; unordered_map<int,int> m; for(int i=0;i<n;i++) { m[a[i]]++; } for(auto u: m) { if(u.second>req) { cout<<u.first<<" "; } } cout<<endl; return 0; }

### Java Program for Elements Appear more than N/K times in Array

import java.util.HashMap; import java.util.Map; import java.util.Scanner; class sum { public static void main(String[] args) { Scanner sr = new Scanner(System.in); int n = sr.nextInt(); int k = sr.nextInt(); int a[] = new int[n]; for(int i=0;i<n;i++) { a[i] = sr.nextInt(); } HashMap<Integer, Integer> m = new HashMap<Integer, Integer>(); for(int i=0;i<n;i++) { int val = m.get(a[i])== null? 0 : m.get(a[i]); m.put(a[i], val+1); } for(Map.Entry u : m.entrySet()) { int val = (int) u.getValue(); if(val > (n/k)) { System.out.print(u.getKey()+" "); } } System.out.println(); } }

7 3 3 4 3 4 3 4 1

3 4

## Complexity Analysis for Elements Appear more than N/K times in Array

### Time Complexity

**O(n)** where** n** is the size of the given array a[]. Here we traverse the whole array and find the freq of each element and store it in a hashmap.

### Space Complexity

**O(n)** where** n** is the size of the given array a[]. Here we use the map to store the frequency of each element.