Given an array arr[] of N integers, the task is to check whether the frequency of the elements in the array is unique or not, or in other words, there are no two distinct numbers in an array with equal frequency. If all the frequency is unique then Print “YES”, else Print “NO”.
Examples:
Input: N = 5, arr = [1, 1, 2, 5, 5]
Output: false
Explanation: The array contains 2 (1’s), 1 (2’s), and 2 (5’s) since the frequency of 1 and 5 are the same i.e. 2 times. Therefore, this array does not satisfy the condition.Input: N = 10, arr = [2, 2, 5, 10, 1, 2, 10, 5, 10, 2]
Output: true
Explanation:
- Number of 1’s -> 1
- Number of 2’s -> 4
- Number of 5’s -> 2
- Number of 10’s -> 3.
Since the number of occurrences of elements present in the array is unique. Therefore, this array satisfies the condition.
Approach: To solve the problem follow the below idea:
Calculate the frequency of each element of the array and check whether all the frequencies are unique or not.
Follow the steps to solve the problem:
- Calculate the frequency of each element and store it in the map.
- Now we have to check the frequencies present in the map are unique or not.
- To do so we can insert all the frequencies in the set and compare the size of the set and map.
- As the set store only unique elements so if the size of the set and the size of the map is equal then our answer is yes else our answer is no because there is at least one frequency that is repeating.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to check if all occurences of// elements are unique or notbool isFrequencyUnique(int n, int arr[]){ // map to store frequencies of elements // in an array unordered_map<int, int> mp; for (int i = 0; i < n; i++) { mp[arr[i]]++; } // set to store the unique frequencies unordered_set<int> st; for (auto x : mp) { st.insert(x.second); } // Returns true if unique frequencies is equal // to total frequencies i.e all frequencies // are unique return st.size() == mp.size();}// Drivers codeint main(){ int arr[] = { 2, 2, 5, 10, 1, 2, 10, 5, 10, 2 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call if (isFrequencyUnique(n, arr)) { cout << "YES\n"; } else { cout << "NO\n"; } return 0;} |
Java
import java.util.*;public class GFG { // Function to check if all occurrences of elements are // unique or not static boolean isFrequencyUnique(int n, int[] arr) { // Map to store frequencies of elements in an array Map<Integer, Integer> mp = new HashMap<>(); for (int i = 0; i < n; i++) { mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1); } // Set to store the unique frequencies Set<Integer> st = new HashSet<>(); for (Map.Entry<Integer, Integer> entry : mp.entrySet()) { st.add(entry.getValue()); } // Returns true if unique frequencies are equal to // total frequencies i.e., all frequencies are // unique return st.size() == mp.size(); } // Driver code public static void main(String[] args) { int[] arr = { 2, 2, 5, 10, 1, 2, 10, 5, 10, 2 }; int n = arr.length; // Function Call if (isFrequencyUnique(n, arr)) { System.out.println("YES"); } else { System.out.println("NO"); } }}// This code is contributed by shivamgupta0987654321 |
Python
# Function to check if all occurrences of# elements are unique or notdef isFrequencyUnique(arr): # Dictionary to store frequencies of elements freq_dict = {} # Count the frequencies of elements for num in arr: if num in freq_dict: freq_dict[num] += 1 else: freq_dict[num] = 1 # Set to store the unique frequencies unique_freqs = set(freq_dict.values()) # Returns True if unique frequencies are equal # to the total frequencies, i.e., all frequencies # are unique return len(unique_freqs) == len(freq_dict)# Driver codearr = [2, 2, 5, 10, 1, 2, 10, 5, 10, 2]# Function Callif isFrequencyUnique(arr): print("YES")else: print("NO") |
C#
// C# code for the above approach:using System;using System.Collections.Generic;class Program{ // Function to check if all occurences of // elements are unique or not static bool IsFrequencyUnique(int n, int[] arr) { // dictionary to store frequencies of elements // in an array Dictionary<int, int> mp = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { if (mp.ContainsKey(arr[i])) { mp[arr[i]]++; } else { mp[arr[i]] = 1; } } // set to store the unique frequencies HashSet<int> st = new HashSet<int>(); foreach (var x in mp) { st.Add(x.Value); } // Returns true if unique frequencies is equal // to total frequencies i.e all frequencies // are unique return st.Count == mp.Count; } // Drivers code static void Main(string[] args) { int[] arr = { 2, 2, 5, 10, 1, 2, 10, 5, 10, 2 }; int n = arr.Length; // Function Call if (IsFrequencyUnique(n, arr)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }} |
Javascript
function isFrequencyUnique(arr) { // Map to store frequencies of // elements in an array const frequencyMap = new Map(); for (const num of arr) { if (!frequencyMap.has(num)) { frequencyMap.set(num, 0); } frequencyMap.set(num, frequencyMap.get(num) + 1); } // Set to store the unique frequencies const uniqueFrequencies = new Set(); for (const freq of frequencyMap.values()) { uniqueFrequencies.add(freq); } return uniqueFrequencies.size === frequencyMap.size;}// Driver codeconst arr = [2, 2, 5, 10, 1, 2, 10, 5, 10, 2];// Function Callif (isFrequencyUnique(arr)) { console.log("YES");} else { console.log("NO");} |
Output
YES
Time Complexity: O(N), we just need to traverse the array and map for once only.
Auxillary space: O(N), we need a frequency map and set to check the frequency of elements is unique or not.
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!
Share your thoughts in the comments