Given an array arr[] of size N, and an integer K representing a digit, the task is to print the given array in increasing order according to the increasing frequency of the digit K in the array elements.
Examples:
Input: arr[] = {15, 66, 26, 91}, K = 6
Output: 15 91 26 66
Explanation:
The frequency of digit 6 in array elements is {0, 2, 1, 0}. The elements in increasing order of frequency of the digit 6 in {15, 91, 26, 66}.Input: arr[] = {20, 21, 0}, K = 0
Output: 21 20 0
Explanation:
The frequency of digit 0 in array elements is {1, 0, 1}. The elements in increasing order of frequency of the digit 0 is {21, 20, 0}.
Approach: The idea is to count the occurrences of the digit K for each element of the array and sort the array according to it. Follow the steps below to solve the problem:
- Initialize a multimap, say mp, to store occurrences of K in each element in sorted order.
- Traverse the given array arr[] using the variable i and perform the following:
- Store the occurrences of digit K in arr[i] in a variable cnt.
- Insert a pair of cnt and arr[i] in mp.
- Print the array elements in mp to get the required sorted order.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;Â
// Function to count the occurrences// of digit K in an elementint countOccurrences(int num, int K){Â Â Â Â // If num and K are both 0Â Â Â Â if (K == 0 && num == 0)Â Â Â Â Â Â Â Â return 1;Â
    // Initialize count as 0    int count = 0;Â
    // Count for occurrences of digit K    while (num > 0) {        if (num % 10 == K)            count++;        num /= 10;    }Â
    // Return the count    return count;}Â
// Function to print the given array// in increasing order of the digit// K in the array elementsvoid sortOccurrences(int arr[],                     int N, int K){    // Stores the occurrences of K    // in each element    multimap<int, int> mp;Â
    // Traverse the array    for (int i = 0; i < N; i++) {Â
        // Count the frequency        // of K in arr[i]        int count = countOccurrences(            arr[i], K);Â
        // Insert elements in mp        mp.insert(pair<int, int>(            count, arr[i]));    }Â
    // Print the elements in the map, mp    for (auto& itr : mp) {        cout << itr.second << " ";    }}Â
// Driver Codeint main(){Â Â Â Â int arr[] = { 15, 66, 26, 91 };Â Â Â Â int K = 6;Â Â Â Â int N = sizeof(arr) / sizeof(arr[0]);Â
    // Function Call    sortOccurrences(arr, N, K);Â
    return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;Â
class GFG {Â
  // Function to count the occurrences  // of digit K in an element  static int countOccurrences(int num, int K)  {    // If num and K are both 0    if (K == 0 && num == 0)      return 1;Â
    // Initialize count as 0    int count = 0;Â
    // Count for occurrences of digit K    while (num > 0) {      if (num % 10 == K)        count++;      num /= 10;    }Â
    // Return the count    return count;  }Â
  // Pair class  static class Pair {Â
    int idx;    int freq;Â
    Pair(int idx, int freq)    {      this.idx = idx;      this.freq = freq;    }  }Â
  // Function to print the given array  // in increasing order of the digit  // K in the array elements  static void sortOccurrences(int arr[], int N, int K)  {Â
    // Stores the Pair with index    // and occurrences of K of each element    Pair mp[] = new Pair[N];Â
    // Traverse the array    for (int i = 0; i < N; i++) {Â
      // Count the frequency      // of K in arr[i]      int count = countOccurrences(arr[i], K);Â
      // Insert Pair in mp      mp[i] = new Pair(i, count);    }Â
    // sort the mp in increasing order of freq    // if freq equal then according to index    Arrays.sort(mp, (p1, p2) -> {      if (p1.freq == p2.freq)        return p1.idx - p2.idx;      return p1.freq - p2.freq;    });Â
    // Print the elements in the map, mp    for (Pair p : mp) {      System.out.print(arr[p.idx] + " ");    }  }Â
  // Driver Code  public static void main(String[] args)  {Â
    int arr[] = { 15, 66, 26, 91 };    int K = 6;    int N = arr.length;Â
    // Function Call    sortOccurrences(arr, N, K);  }}Â
// This code is contributed by Kingash. |
Python3
# Python program for the above approachÂ
# Function to count the occurrences# of digit K in an elementdef countOccurrences( num, K):       # If num and K are both 0    if (K == 0 and num == 0):        return 1           # Initialize count as 0    count = 0         # Count for occurrences of digit K    while (num > 0):        if (num % 10 == K):            count += 1        num //= 10             # Return the count    return countÂ
# Function to print the given array# in increasing order of the digit# K in the array elementsdef sortOccurrences(arr, N, K):       # Stores the occurrences of K    # in each element    mp = []         # Traverse the array    for i in range(N):               # Count the frequency        # of K in arr[i]        count = countOccurrences(arr[i], K)                 # Insert elements in mp        mp.append([count, arr[i]])Â
    # Print the elements in the map, mp    mp = sorted(mp)         for itr in mp:        print(itr[1], end = ' ')Â
# Driver Codearr = [ 15, 66, 26, 91 ]K = 6N = len(arr)Â
# Function CallsortOccurrences(arr, N, K);Â
# This code is contributed by rohitsingh07052. |
C#
// C# program for the above approachusing System;Â
public class GFG {Â
  // Function to count the occurrences  // of digit K in an element  static int countOccurrences(int num, int K)  {    // If num and K are both 0    if (K == 0 && num == 0)      return 1;Â
    // Initialize count as 0    int count = 0;Â
    // Count for occurrences of digit K    while (num > 0) {      if (num % 10 == K)        count++;      num /= 10;    }Â
    // Return the count    return count;  }Â
  // Pair class  class Pair : IComparable<Pair> {Â
    public int idx;    public int freq;Â
    public Pair(int idx, int freq)    {      this.idx = idx;      this.freq = freq;    }      public int CompareTo(Pair p)      {          if (this.freq == p.freq)            return this.idx - p.idx;          return this.freq - p.freq;Â
      }  }Â
  // Function to print the given array  // in increasing order of the digit  // K in the array elements  static void sortOccurrences(int []arr, int N, int K)  {Â
    // Stores the Pair with index    // and occurrences of K of each element    Pair []mp = new Pair[N];Â
    // Traverse the array    for (int i = 0; i < N; i++) {Â
      // Count the frequency      // of K in arr[i]      int count = countOccurrences(arr[i], K);Â
      // Insert Pair in mp      mp[i] = new Pair(i, count);    }Â
    // sort the mp in increasing order of freq    // if freq equal then according to index    Array.Sort(mp);Â
    // Print the elements in the map, mp    foreach (Pair p in mp) {      Console.Write(arr[p.idx] + " ");    }  }Â
  // Driver Code  public static void Main(String[] args)  {Â
    int []arr = { 15, 66, 26, 91 };    int K = 6;    int N = arr.Length;Â
    // Function Call    sortOccurrences(arr, N, K);  }}Â
// This code is contributed by 29AjayKumar |
Javascript
<script>Â
// JavaScript program for the above approachÂ
// Function to count the occurrences// of digit K in an elementfunction countOccurrences( num, K){       // If num and K are both 0    if (K == 0 && num == 0)        return 1           // Initialize count as 0    count = 0         // Count for occurrences of digit K    while (num > 0){        if (num % 10 == K)            count += 1        num = Math.floor(num/10)    }             // Return the count    return count}Â
// Function to print the given array// in increasing order of the digit// K in the array elementsfunction sortOccurrences(arr, N, K){       // Stores the occurrences of K    // in each element    mp = []         // Traverse the array    for(let i=0;i<N;i++){               // Count the frequency        // of K in arr[i]        let count = countOccurrences(arr[i], K)                 // Insert elements in mp        mp.push([count, arr[i]])    }Â
    // Print the elements in the map, mp    mp.sort()         for([itr1,itr2] of mp)        document.write(itr2,' ')}Â
// Driver Codelet arr = [ 15, 66, 26, 91 ]let K = 6let N = arr.lengthÂ
// Function CallsortOccurrences(arr, N, K)Â
// This code is contributed by shinjanpatraÂ
</script> |
Output:Â
15 91 26 66
Â
Time Complexity: O(N*log10N)
Auxiliary Space: O(N)
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!
