Sort an array according to the increasing frequency of the digit K in the array elements

0 0 6 minutes read

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 element
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;
}
 
// Function to print the given array
// in increasing order of the digit
// K in the array elements
void 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 Code
int 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 approach
import 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 element
def 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 elements
def 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 Code
arr = [ 15, 66, 26, 91 ]
K = 6
N = len(arr)
 
# Function Call
sortOccurrences(arr, N, K);
 
# This code is contributed by rohitsingh07052.

C#

// C# program for the above approach
using 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 element
function 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 elements
function 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 Code
let arr = [ 15, 66, 26, 91 ]
let K = 6
let N = arr.length
 
// Function Call
sortOccurrences(arr, N, K)
 
// This code is contributed by shinjanpatra
 
</script>

Output:

15 91 26 66

Time Complexity: O(N*log₁₀N)
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 zambiatek!