Given an array arr, the task is to print the elements of the array in descending order along with their frequencies.
Examples:
Input: arr[] = {1, 3, 3, 3, 4, 4, 5}
Output: 5 occurs 1 times
4 occurs 2 times
3 occurs 3 times
1 occurs 1 times
Input: arr[] = {1, 1, 1, 2, 3, 4, 9, 9, 10}
Output: 10 occurs 1 times
9 occurs 2 times
4 occurs 1 times
3 occurs 1 times
2 occurs 1 times
1 occurs 3 times
Naive approach: Use some Data-Structure (e.g. multiset) that stores elements in decreasing order and then print the elements one by one with its count and then erase it from the Data-structure. The time complexity will be O(N log N) and the auxiliary space will be O(N) for the Data-structure used.
Below is the implementation of the above approach:
CPP
// C++ program to print the elements in// descending along with their frequencies#include <bits/stdc++.h>using namespace std;// Function to print the elements in descending// along with their frequenciesvoid printElements(int a[], int n){ // A multiset to store elements in decreasing order multiset<int, greater<int> > ms; // Insert elements in the multiset for (int i = 0; i < n; i++) { ms.insert(a[i]); } // Print the elements along with their frequencies while (!ms.empty()) { // Find the maximum element int maxel = *ms.begin(); // Number of times it occurs int times = ms.count(maxel); cout << maxel << " occurs " << times << " times\n"; // Erase the maxel ms.erase(maxel); }}// Driver Codeint main(){ int a[] = { 1, 1, 1, 2, 3, 4, 9, 9, 10 }; int n = sizeof(a) / sizeof(a[0]); printElements(a, n); return 0;} |
Python3
# Function to print the elements in descending# along with their frequenciesdef printElements(a): # A multiset to store elements in decreasing order ms = sorted(a, reverse=True) # Print the elements along with their frequencies while ms: # Find the maximum element maxel = ms[0] # Number of times it occurs times = ms.count(maxel) print(f"{maxel} occurs {times} times") # Remove all occurrences of maxel ms = [x for x in ms if x != maxel]# Driver codeif __name__ == '__main__': a = [1, 1, 1, 2, 3, 4, 9, 9, 10] printElements(a) |
Javascript
// JavaScript program to print the elements in// descending along with their frequencies in reverse order// Function to print the elements in descending// along with their frequencies in reverse orderfunction printElements(a) { // A Map to store elements in decreasing order const ms = new Map(); // Insert elements in the Map for (let i = 0; i < a.length; i++) { const key = a[i]; ms.set(key, (ms.get(key) || 0) + 1); } // Array to store the elements along with their frequencies const elements = []; // Store the elements and their frequencies in the array for (const [key, value] of ms.entries()) { elements.push(`${key} occurs ${value} times`); } // Print the elements along with their frequencies in reverse order for (let i = elements.length - 1; i >= 0; i--) { console.log(elements[i]); }}// Driver Codeconst a = [1, 1, 1, 2, 3, 4, 9, 9, 10];printElements(a); |
Java
import java.util.*;public class Main { // Function to print the elements in descending // along with their frequencies static void printElements(int[] a, int n) { // A TreeMap to store elements in decreasing order TreeMap<Integer, Integer> tm = new TreeMap<>(Collections.reverseOrder()); // Insert elements in the TreeMap for (int i = 0; i < n; i++) { if (tm.containsKey(a[i])) { tm.put(a[i], tm.get(a[i]) + 1); } else { tm.put(a[i], 1); } } // Print the elements along with their frequencies for (Map.Entry<Integer, Integer> entry : tm.entrySet()) { int element = entry.getKey(); int frequency = entry.getValue(); System.out.println(element + " occurs " + frequency + " times"); } } // Driver Code public static void main(String[] args) { int[] a = { 1, 1, 1, 2, 3, 4, 9, 9, 10 }; int n = a.length; printElements(a, n); }} |
C#
using System;using System.Collections.Generic;public class Program { // Function to print the elements in descending // along with their frequencies static void PrintElements(int[] a, int n) { // A SortedDictionary to store elements in decreasing order SortedDictionary<int, int> sd = new SortedDictionary<int, int>(new DescendingComparer()); // Insert elements in the SortedDictionary for (int i = 0; i < n; i++) { if (sd.ContainsKey(a[i])) { sd[a[i]]++; } else { sd[a[i]] = 1; } } // Print the elements along with their frequencies foreach (KeyValuePair<int, int> entry in sd) { int element = entry.Key; int frequency = entry.Value; Console.WriteLine(element + " occurs " + frequency + " times"); } } // Custom comparer to sort the keys in descending order class DescendingComparer : IComparer<int> { public int Compare(int x, int y) { return y.CompareTo(x); } } // Driver Code public static void Main() { int[] a = { 1, 1, 1, 2, 3, 4, 9, 9, 10 }; int n = a.Length; PrintElements(a, n); }} |
Output:
10 occurs 1 times 9 occurs 2 times 4 occurs 1 times 3 occurs 1 times 2 occurs 1 times 1 occurs 3 times
Time Complexity: O(N*logN), as we are using a loop to traverse N times and in each traversal, we are doing a multiset operation which will cost us logN time.
Auxiliary Space: O(N), as we are using extra space for the multiset.
Efficient Approach: Sort the array in descending order and then start printing the elements from the beginning along with their frequencies.
Below is the implementation of the above approach:
C++
// C++ program to print the elements in// descending along with their frequencies#include <bits/stdc++.h>using namespace std;// Function to print the elements in descending// along with their frequenciesvoid printElements(int a[], int n){ // Sorts the element in decreasing order sort(a, a + n, greater<int>()); int cnt = 1; // traverse the array elements for (int i = 0; i < n - 1; i++) { // Prints the number and count if (a[i] != a[i + 1]) { cout << a[i] << " occurs " << cnt << " times\n"; cnt = 1; } else cnt += 1; } // Prints the last step cout << a[n - 1] << " occurs " << cnt << " times\n";}// Driver Codeint main(){ int a[] = { 1, 1, 1, 2, 3, 4, 9, 9, 10 }; int n = sizeof(a) / sizeof(a[0]); printElements(a, n); return 0;} |
Java
// Java program to print the elements in// descending along with their frequenciesimport java.util.*;class GFG{// Function to print the elements in descending// along with their frequenciesstatic void printElements(int a[], int n){ // Sorts the element in decreasing order Arrays.sort(a); a = reverse(a); int cnt = 1; // traverse the array elements for (int i = 0; i < n - 1; i++) { // Prints the number and count if (a[i] != a[i + 1]) { System.out.print(a[i]+ " occurs " + cnt + " times\n"); cnt = 1; } else cnt += 1; } // Prints the last step System.out.print(a[n - 1]+ " occurs " + cnt + " times\n");}static int[] reverse(int a[]){ int i, n = a.length, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a;}// Driver Codepublic static void main(String[] args){ int a[] = { 1, 1, 1, 2, 3, 4, 9, 9, 10 }; int n = a.length; printElements(a, n);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to print the elements in # descending along with their frequencies # Function to print the elements in # descending along with their frequencies def printElements(a, n) : # Sorts the element in decreasing order a.sort(reverse = True) cnt = 1 # traverse the array elements for i in range(n - 1) : # Prints the number and count if (a[i] != a[i + 1]) : print(a[i], " occurs ", cnt, "times") cnt = 1 else : cnt += 1 # Prints the last step print(a[n - 1], "occurs", cnt, "times") # Driver Code if __name__ == "__main__" : a = [ 1, 1, 1, 2, 3, 4, 9, 9, 10 ] n = len(a) printElements(a, n) # This code is contributed by Ryuga |
C#
// C# program to print the elements in// descending along with their frequenciesusing System;class GFG{// Function to print the elements in descending// along with their frequenciesstatic void printElements(int []a, int n){ // Sorts the element in decreasing order Array.Sort(a); a = reverse(a); int cnt = 1; // traverse the array elements for (int i = 0; i < n - 1; i++) { // Prints the number and count if (a[i] != a[i + 1]) { Console.Write(a[i]+ " occurs " + cnt + " times\n"); cnt = 1; } else cnt += 1; } // Prints the last step Console.Write(a[n - 1]+ " occurs " + cnt + " times\n");}static int[] reverse(int []a){ int i, n = a.Length, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a;}// Driver Codepublic static void Main(String[] args){ int []a = { 1, 1, 1, 2, 3, 4, 9, 9, 10 }; int n = a.Length; printElements(a, n);}}// This code is contributed by PrinciRaj1992 |
PHP
<?php// PHP program to print the elements in// descending along with their frequencies// Function to print the elements in // descending along with their frequenciesfunction printElements(&$a, $n){ // Sorts the element in // decreasing order rsort($a); $cnt = 1; // traverse the array elements for ($i = 0; $i < $n - 1; $i++) { // Prints the number and count if ($a[$i] != $a[$i + 1]) { echo ($a[$i]); echo (" occurs " ); echo $cnt ; echo (" times\n"); $cnt = 1; } else $cnt += 1; } // Prints the last step echo ($a[$n - 1]); echo (" occurs "); echo $cnt; echo (" times\n");}// Driver Code$a = array(1, 1, 1, 2, 3, 4, 9, 9, 10 );$n = sizeof($a);printElements($a, $n);// This code is contributed// by Shivi_Aggarwal?> |
Javascript
<script>// javascript program to print the elements in// descending along with their frequencies // Function to print the elements in descending// along with their frequencies function printElements(a, n) { // Sorts the element in decreasing order a=a.sort(compare); a = reverse(a); var cnt = 1; // traverse the array elements for (var i = 0; i < n - 1; i++) { // Prints the number and count if (a[i] != a[i + 1]) { document.write(a[i]+ " occurs " + cnt + " times" + "<br>"); cnt = 1; } else cnt += 1; } // Prints the last step document.write(a[n - 1]+ " occurs " + cnt + " times" + "<br>");} function reverse(a){ var i, n = a.length, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a;}function compare(a, b) { if (a < b) { return -1; } else if (a > b) { return 1; } else { return 0; }} // Driver Code var a = [ 1, 1, 1, 2, 3, 4, 9, 9, 10 ]; var n = a.length; printElements(a, n); // This code is contributed by bunnyram19.</script> |
Output:
10 occurs 1 times 9 occurs 2 times 4 occurs 1 times 3 occurs 1 times 2 occurs 1 times 1 occurs 3 times
Time Complexity: O(N*logN), as we are using the sort function which will cost us O(N*logN) time.
Auxiliary Space: O(1), as we are not using any extra space.
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!
