“Given an array of N integers, and an integer K. Write a program to find all the elements in an array that appear more than n/k times.”
Examples:
Example 1:
Input:
N = 8,
K=4,
array[] = {3,1,2,2,1,2,3,3}
Output: {2,3}
Explanation:
The frequency of 2 in array appears more
than n/k times i.e. (8/4=2) so we will
print it, and 3 also has occurred 3 time
which is more than 2 (n/k) times.
Example 2:
Input:
N = 5
,K=2,
array[]={1,2,3,4,5}
Output: null
Explanation: Here n/k is (5/2=2 in integers)
and there are not any integers present whose
frequency is not more than 2 , so we will
return null.
NOTE- The element should be more than n/k elements, not more than equals to.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1:
Intuition:
Here the position of elements is not required so what we can do that we can put all the same elements together which means we can sort it.
Approach:
First sort the elements then count the frequency of distinct elements by checking its adjacent elements are equal or not if the frequency of elements is greater than n/k then, print the array element.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
void solution(int arr[], int n, int k) {
sort(arr, arr + n);
// Traverse the array
for (int i = 0; i < n;) {
int cnt = 1;
while ((i + 1) < n &&
arr[i] == arr[i + 1]) {
cnt++;
i++;
}
if (cnt > (n / k)) {
cout << arr[i] << " ";
}
i++;
}
}
int main() {
// your code goes here
int n=8, k=4;
int arr[]={3,1,2,2,1,2,3,3};
solution(arr, n, k);
return 0;
}
Output: 2 3
Time Complexity: O(n*logn), as we are sorting the array.
Space Complexity:- O(1)
Java Code
import java.util.*;
class TUF{
static void solution(int arr[], int n, int k) {
Arrays.sort(arr);
// Traverse the array
for (int i = 0; i < n;) {
int cnt = 1;
while ((i + 1) < n && arr[i] == arr[i + 1]) {
cnt++;
i++;
}
if (cnt > (n / k)) {
System.out.print(arr[i]+" ");
}
i++;
}
}
public static void main(String args[]) {
// your code goes here
int n=8, k=4;
int arr[]={3,1,2,2,1,2,3,3};
solution(arr, n, k);
}
}
Output: 2 3
Time Complexity: O(n*logn), as we are sorting the array.
Space Complexity:- O(1)
Solution 2: Using Maps
Intuition :
What we really need is to store the frequency of each element in some data structure and then compare it with n/k.
Approach:
Take an unordered map and traverse through the array and keep incrementing the value in the map every time that key appears in the array. At last, compare it with a variable comp which stores the value of n/k. And keep storing the answer in a dynamic array or directly printing it.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
void solution(int arr[], int n, int k) {
int comp = n / k;
unordered_map < int, int > mp;
for (int i = 0; i < n; i++) {
mp[arr[i]]++;
}
for (auto x: mp) {
if (x.second > comp)
cout << x.first << " ";
}
}
int main() {
// your code goes here
int n=8, k=4;
int arr[]={3,1,2,2,1,2,3,3};
solution(arr, n, k);
}
Output: 2 3
Time Complexity:
O(n)- as we are traversing through the array only once.
Space Complexity:
O(n)- if all the elements are unique in the array so every element will take space.
Java Code
import java.util.*;
class TUF{
static void solution(int arr[], int n, int k) {
int comp = n / k;
HashMap<Integer, Integer > map=new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(arr[i], map.getOrDefault(arr[i],0)+1);
}
for(int x:map.keySet()){
if(map.get(x)>comp)
System.out.print(x+" ");
}
}
public static void main(String args[]) {
// your code goes here
int n=8, k=4;
int arr[]={3,1,2,2,1,2,3,3};
solution(arr, n, k);
}
}Output: 2 3
Time Complexity:
O(n)- as we are traversing through the array only once.
Space Complexity:
O(n)- if all the elements are unique in the array so every element will take space.
Special thanks to Ayush Pandey for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article