Tutorialspoint.dev

Difference between highest and least frequencies in an array

Given an array, find the difference between highest occurrence and least occurrence of any number in an array

Examples:

Input  : arr[] = [7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5]
Output : 2
Lowest occurring element (5) occurs once.
Highest occurring element (1 or 7) occurs 3 times

Input  : arr[] = [1, 1, 1, 3, 3, 3]
Output : 0



A simple solution is to use two loops to count frequency of every element and keep track of maximum and minimum frequencies.

A better solution is to sort the array in O(n log n) and check
consecutive element’s occurrence and compare their count respectively.

C++

// CPP code to find the difference between highest
// and least frequencies
#include <bits/stdc++.h>
using namespace std;
  
int findDiff(int arr[], int n)
{
    // sort the array
    sort(arr, arr + n);
  
    int count = 0, max_count = 0, min_count = n;
    for (int i = 0; i < (n - 1); i++) {
  
        // checking consecutive elements
        if (arr[i] == arr[i + 1]) {
            count += 1;
            continue;
        }
        else {
            max_count = max(max_count, count);
            min_count = min(min_count, count);
            count = 0;
        }
    }
  
    return (max_count - min_count);
}
  
// Driver code
int main()
{
    int arr[] = { 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    cout << findDiff(arr, n) << " ";
    return 0;
}

Java

// JAVA Code for Difference between
// highest and least frequencies
// in an array
import java.util.*;
  
class GFG {
  
    static int findDiff(int arr[], int n)
    {
        // sort the array
        Arrays.sort(arr);
  
        int count = 0, max_count = 0,
            min_count = n;
  
        for (int i = 0; i < (n - 1); i++) {
  
            // checking consecutive elements
            if (arr[i] == arr[i + 1]) {
                count += 1;
                continue;
            }
            else {
                max_count = Math.max(max_count,
                                     count);
  
                min_count = Math.min(min_count,
                                     count);
                count = 0;
            }
        }
  
        return (max_count - min_count);
    }
  
    // Driver program to test above function
    public static void main(String[] args)
    {
  
        int arr[] = { 7, 8, 4, 5, 4, 1,
                      1, 7, 7, 2, 5 };
        int n = arr.length;
  
        System.out.println(findDiff(arr, n));
    }
}
  
// This code is contributed by Arnav Kr. Mandal.

Python3

# Python3 code to find the difference 
# between highest nd least frequencies
  
def findDiff(arr, n):
      
    # sort the array
    arr.sort()
      
    count = 0; max_count = 0; min_count = n
    for i in range(0, (n-1)):
  
        # checking consecutive elements
        if arr[i] == arr[i + 1]:
            count += 1
            continue
        else:
            max_count = max(max_count, count)
            min_count = min(min_count, count)
            count = 0
    return max_count - min_count
  
# Driver Code
arr = [ 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 ]
n = len(arr)
print (findDiff(arr, n))
  
# This code is contributed by Shreyanshi Arun.

C#

// C# Code for Difference between
// highest and least frequencies
// in an array
using System;
  
class GFG {
  
    static int findDiff(int[] arr, int n)
    {
          
        // sort the array
        Array.Sort(arr);
  
        int count = 0, max_count = 0,
            min_count = n;
  
        for (int i = 0; i < (n - 1); i++) {
  
            // checking consecutive elements
            if (arr[i] == arr[i + 1]) {
                count += 1;
                continue;
            }
            else {
                max_count = Math.Max(max_count,
                                    count);
  
                min_count = Math.Min(min_count,
                                    count);
                count = 0;
            }
        }
  
        return (max_count - min_count);
    }
  
    // Driver program to test above function
    public static void Main()
    {
  
        int[] arr = { 7, 8, 4, 5, 4, 1,
                       1, 7, 7, 2, 5 };
        int n = arr.Length;
  
        Console.WriteLine(findDiff(arr, n));
    }
}
  
// This code is contributed by vt_m.

PHP

<?php
// PHP code to find the 
// difference between highest
// and least frequencies
  
// function that 
// returns difference
function findDiff($arr, $n)
{
      
    // sort the array
    sort($arr);
  
    $count = 0; $max_count = 0; 
    $min_count = $n;
    for ($i = 0; $i < ($n - 1); $i++)
    {
  
        // checking consecutive elements
        if ($arr[$i] == $arr[$i + 1])
        {
            $count += 1;
            continue;
        }
        else
        {
            $max_count = max($max_count, $count);
            $min_count = min($min_count, $count);
            $count = 0;
        }
    }
  
    return ($max_count - $min_count);
}
  
// Driver Code
$arr = array(7, 8, 4, 5, 4, 1,
             1, 7, 7, 2, 5);
$n = sizeof($arr);
  
echo(findDiff($arr, $n) . " ");
  
// This code is contributed by Ajit.
?>


Output:

 2

An efficient solution is to use hashing. We count frequencies of all elements and finally traverse the hash table to find maximum and minimum.

Below is the implementation.

C++

// CPP code to find the difference between highest
// and least frequencies
#include <bits/stdc++.h>
using namespace std;
  
int findDiff(int arr[], int n)
{
    // Put all elements in a hash map
    unordered_map<int, int> hm;
    for (int i = 0; i < n; i++)
        hm[arr[i]]++;
  
    // Find counts of maximum and minimum
    // frequent elements
    int max_count = 0, min_count = n;
    for (auto x : hm) {
        max_count = max(max_count, x.second);
        min_count = min(min_count, x.second);
    }
  
    return (max_count - min_count);
}
  
// Driver
int main()
{
    int arr[] = { 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    cout << findDiff(arr, n) << " ";
    return 0;
}

Python3

# Python code to find the difference between highest 
# and least frequencies 
  
from collections import defaultdict
def findDiff(arr,n):
  
    # Put all elements in a hash map
    mp = defaultdict(lambda:0)
    for i in range(n):
        mp[arr[i]]+=1
  
    # Find counts of maximum and minimum 
    # frequent elements 
    max_count=0;min_count=n
    for key,values in mp.items():
        max_count= max(max_count,values)
        min_count = min(min_count,values)
  
    return max_count-min_count
  
  
# Driver code
arr = [ 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5]
n = len(arr)
print(findDiff(arr,n))
  
# This code is contributed by Shrikant13


Output:

 2

Time Complexity : O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter