Given an array of integers arr[] of size N, the task is to find the maximum element in the array whose frequency equals to it’s value
Examples:
Input: arr[] = {3, 2, 2, 3, 4, 3}
Output: 3
Frequency of element 2 is 2
Frequency of element 3 is 3
Frequency of element 4 is 1
2 and 3 are elements which have same frequency as it’s value and 3 is the maximum.
Input: arr[] = {1, 2, 3, 4, 5, 6}
Output: 1
Approach: Store the frequency of every element of the array using the map, and finally find out the maximum of those element whose frequency is equal to their value.
Algorithm:
Step 1: Start
Step 2: Create a static function with an int return type name “find_maxm” which takes an array and an integer value as input parameter.
a. Create a map “mpp” of integer type to store the frequency of each element in the array arr.
b. start a for loop and traverse through i = 0 to n-1
c. For each element in the array, increment the frequency count in the map “mpp”.
Step 3: Create an int variable “ans” and initialize it with 0.
Step 4: Traverse the map “mpp” using a for-each loop.
a. Set x.first to value and x.second to freq for each key-value pair x in the map.
b. Verify that the value and frequency are equivalent.
c. If the answer is yes, see if it exceeds the current value of ans. Update ans with the value if the answer is yes.
d. Give the ans value back.
Step 5: End
Below is the implementation of the above approach:
CPP
// C++ program to find the maximum element // whose frequency equals to it’s value#include <bits/stdc++.h>using namespace std;// Function to find the maximum element // whose frequency equals to it’s valueint find_maxm(int arr[], int n){ // Hash map for counting frequency map<int, int> mpp; for (int i = 0; i < n; i++) { // Counting freq of each element mpp[arr[i]] += 1; } int ans = 0; for (auto x : mpp) { int value = x.first; int freq = x.second; // Check if value equals to frequency // and it is the maximum element or not if (value == freq) { ans = max(ans, value); } } return ans;}// Driver codeint main(){ int arr[] = { 3, 2, 2, 3, 4, 3 }; // Size of array int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << find_maxm(arr, n); return 0;} |
Java
// Java program to find the maximum element // whose frequency equals to it’s valueimport java.util.*;class GFG{ // Function to find the maximum element // whose frequency equals to it’s valuestatic int find_maxm(int arr[], int n){ // Hash map for counting frequency HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); for (int i = 0; i < n; i++) { // Counting freq of each element if(mp.containsKey(arr[i])){ mp.put(arr[i], mp.get(arr[i])+1); }else{ mp.put(arr[i], 1); } } int ans = 0; for (Map.Entry<Integer,Integer> x : mp.entrySet()) { int value = x.getKey(); int freq = x.getValue(); // Check if value equals to frequency // and it is the maximum element or not if (value == freq) { ans = Math.max(ans, value); } } return ans;} // Driver codepublic static void main(String[] args){ int arr[] = { 3, 2, 2, 3, 4, 3 }; // Size of array int n = arr.length; // Function call System.out.print(find_maxm(arr, n)); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to find the maximum element # whose frequency equals to it’s value # Function to find the maximum element # whose frequency equals to it’s value def find_maxm(arr, n) : # Hash map for counting frequency mpp = {} for i in range(0,n): # Counting freq of each element if(arr[i] in mpp): mpp.update( {arr[i] : mpp[arr[i]] + 1} ) else: mpp[arr[i]] = 1 ans = 0 for value,freq in mpp.items(): # Check if value equals to frequency # and it is the maximum element or not if (value == freq): ans = max(ans, value) return ans# Driver code arr = [ 3, 2, 2, 3, 4, 3 ] # Size of array n = len(arr)# Function call print(find_maxm(arr, n))# This code is contributed by Sanjit_Prasad |
C#
// C# program to find the maximum element // whose frequency equals to it’s valueusing System;using System.Collections.Generic;class GFG{ // Function to find the maximum element // whose frequency equals to it’s valuestatic int find_maxm(int []arr, int n){ // Hash map for counting frequency Dictionary<int,int> mp = new Dictionary<int,int>(); for (int i = 0; i < n; i++) { // Counting freq of each element if(mp.ContainsKey(arr[i])){ mp[arr[i]] = mp[arr[i]]+1; }else{ mp.Add(arr[i], 1); } } int ans = 0; foreach (KeyValuePair<int,int> x in mp) { int value = x.Key; int freq = x.Value; // Check if value equals to frequency // and it is the maximum element or not if (value == freq) { ans = Math.Max(ans, value); } } return ans;} // Driver codepublic static void Main(String[] args){ int []arr = { 3, 2, 2, 3, 4, 3 }; // Size of array int n = arr.Length; // Function call Console.Write(find_maxm(arr, n));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to find the maximum element // whose frequency equals to it’s value// Function to find the maximum element // whose frequency equals to it’s valuefunction find_maxm(arr, n){ // Hash map for counting frequency var mpp = new Map(); for (var i = 0; i < n; i++) { // Counting freq of each element if(mpp.has(arr[i])) mpp.set(arr[i], mpp.get(arr[i])+1) else mpp.set(arr[i], 1) } var ans = 0; mpp.forEach((value, key) => { var value = value; var freq = key; // Check if value equals to frequency // and it is the maximum element or not if (value == freq) { ans = Math.max(ans, value); } }); return ans;}// Driver codevar arr = [3, 2, 2, 3, 4, 3 ];// Size of arrayvar n = arr.length;// Function calldocument.write( find_maxm(arr, n));// This code is contributed by famously.</script> |
Output
3
Time Complexity : O(N)
Space Complexity : O(N) for Hash Map
where N is length of array
Approach : Using Binary Search
The idea of using Binary Search is that we can use the indices values of elements after sorting the array.
If the difference of indices is equal to its value then we can say that the no of appearances of the element is equal to its value.
Below is the implementation of the above idea.
C++
#include <iostream>#include <algorithm>using namespace std;int binarySearch(int arr[], int target, int left, int right) { int index = -1; while (left <= right) { int middle = left + (right - left) / 2; // if found, keep searching forward to the last occurrence, // otherwise, search to the left if (arr[middle] == target) { index = middle; left = middle + 1; } else { right = middle - 1; } } return index;}int find_max(int arr[], int n) { sort(arr, arr + n); int max_num = -1; int i = 0; while (i < n) { int current = arr[i]; // search the last occurrence from the current index int j = binarySearch(arr, current, i, n - 1); // if the number of occurrences of the current element equals the // current element itself, update the lucky integer if ((j - i) + 1 == current) { max_num = current; } // move index to the next different element i = j + 1; } return max_num;}// Driver codeint main() { int arr[] = { 3, 2, 2, 3, 4, 3 }; // Size of array int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << find_max(arr, n); return 0;} |
Java
// Java program to find the maximum element// whose frequency equals to it’s valueimport java.util.*;class GFG { // Function to find the maximum element // whose frequency equals to it’s value public static int find_max(int[] arr,int n) { Arrays.sort(arr); int max_num = -1; int i = 0; while(i < arr.length){ int current = arr[i]; // search the last occurence from the current index int j = binarySearch(arr, current, i, arr.length - 1); // if the number of occurences of current element equal the //current element itself, update the lucky integer if((j - i) + 1 == current){ max_num = current; } // move index to the next different element i = j + 1; } return max_num; } public static int binarySearch(int[] arr, int target, int left, int right){ int index = -1; while(left <= right){ int middle = left + (right - left) / 2; // if found, keep searching fwd to the last occurence, //otherwise, search to the left if(arr[middle] == target){ index = middle; left = middle + 1; } else { right = middle - 1; } } return index; } // Driver code public static void main(String[] args) { int arr[] = { 3, 2, 2, 3, 4, 3 }; // Size of array int n = arr.length; // Function call System.out.print(find_max(arr, n)); }}// This code is contributed by aeroabrar_31 |
Python3
def binarySearch(arr, target, left, right): index = -1 while left <= right: middle = left + (right - left) // 2 # if found, keep searching forward to the last occurrence, # otherwise, search to the left if arr[middle] == target: index = middle left = middle + 1 else: right = middle - 1 return indexdef find_max(arr, n): arr.sort() max_num = -1 i = 0 while i < n: current = arr[i] # search the last occurrence from the current index j = binarySearch(arr, current, i, n - 1) # if the number of occurrences of the current element equals the # current element itself, update the lucky integer if (j - i) + 1 == current: max_num = current # move index to the next different element i = j + 1 return max_num# Driver codeif __name__ == "__main__": arr = [3, 2, 2, 3, 4, 3] # Size of array n = len(arr) # Function call print(find_max(arr, n)) |
C#
using System;class Program{ static void Main(string[] args) { int[] arr = { 3, 2, 2, 3, 4, 3 }; // Function call Console.WriteLine(FindMax(arr)); } static int FindMax(int[] arr) { // Sort the array in ascending order Array.Sort(arr); int maxNum = -1; int i = 0; while (i < arr.Length) { int current = arr[i]; // Search for the last occurrence of the current element int j = BinarySearch(arr, current, i, arr.Length - 1); // If the number of occurrences of the current element equals // the current element itself, update the lucky integer if ((j - i) + 1 == current) { maxNum = current; } // Move the index to the next different element i = j + 1; } return maxNum; } static int BinarySearch(int[] arr, int target, int left, int right) { int index = -1; while (left <= right) { int middle = left + (right - left) / 2; // If found, keep searching forward to the last occurrence, // otherwise, search to the left if (arr[middle] == target) { index = middle; left = middle + 1; } else { right = middle - 1; } } return index; }} |
Output
3
Time Complexity : O(N logN)
Space Complexity : O(1)
So far, we have reduced the space complexity from linear to constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
