Minimize the maximum frequency of Array elements by replacing them only once ❤️

Given an array A[] of length N, the task is to minimize the maximum frequency of any array element by performing the following operation only once:

Choose any random set (say S) of indices i (0 ? i ? N-1) of the array such that every element of S is the same and
Replace every element of that index with any other number.

Examples:

Input: A[] = {1 ,4 ,4 ,1 ,4 , 4}
Output: 2
Explanation: Choose index i = {1, 2} and perform the operation
{ 1, 4, 4, 1, 4, 4 }? { 1, 5, 5, 1, 4, 4 }.
The highest frequency is of element 4, 5 and 1 which is 2.
This is the minimum possible value of highest frequency of an element.

Input: A[] = {5 ,5 ,5 ,5 ,5 }
Output: 3

Approach: The problem can be solved based on the following observation:

Let N be the element with the maximum frequency in A[] and M be the element with the second maximum frequency in A[]. It is possible that M does not exist.

If M exist then maximum frequency = freq_N.

Indices such that A[i] = N, should be chosen because the final value of freq_N should be minimized and it is always better to replace with number(num) such that num ? M. Only a maximum of ? freq_N/2? elements should be replaced because if we replace more, then num becomes the new element with the maximum frequency

Hence, it is optimal to replace ? freq_N/2? occurrences of N to some num ? M.Now, freq_N – ? freq_N/2? is the final frequency of N and freq_M is the final frequency of M.

The maximum among these two i.e. Max( freq_N – ? freq_N/2?, freq_M ) has to be the answer because the frequency of num = ?freq_N/2? ?( freq_N – ? freq_N/2?) = frequency of N .

If M does not exist it means freq_M = 0 . So , the answer is freq_N – ? freq_N/2?.

Follow the below steps to implement the above idea:

Find the frequency of the most frequent and the second most frequent element.
Compare those frequencies.
- Based on the frequency, follow the above conditions to find the minimized value of maximum frequency.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to minimize frequency of
// most frequent element
int minFreq(int arr[], int n)
{
 
    int b[n];
    for (int i = 0; i < n; i++) {
        b[i] = 0;
    }
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++) {
        if (mp.count(arr[i]) < 0) {
            mp[arr[i]] = 1;
        }
        else {
            mp[arr[i]]++;
        }
    }
 
    for (int i = 0; i < n; i++) {
        if (mp[arr[i]] != -1) {
 
            // Count frequency of each element
            b[i] = mp[arr[i]];
            mp[arr[i]] = -1;
        }
    }
 
    // Last index value is maximum
    // frequency of any element
    sort(b, b + n);
    if (b[n - 1] % 2 == 0) {
        b[n - 1] = b[n - 1] / 2;
    }
    else {
        b[n - 1] = (b[n - 1] + 1) / 2;
    }
 
    // Last index value is possible
    // minimum frequency of
    // most frequent element
    sort(b, b + n);
    return b[n - 1];
}
 
int main()
{
 
    int A[] = { 1, 4, 4, 1, 4, 4 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function call
    cout << (minFreq(A, N));
    return 0;
}
 
// This code is contributed by akashish__

Java

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to minimize frequency of 
    // most frequent element
    public static int minFreq(int arr[], int n)
    {
 
        int[] b = new int[n];
        Map<Integer, Integer> mp = new HashMap<>();
        for (int i = 0; i < n; i++) {
            mp.put(arr[i], mp.get(arr[i]) == null
                               ? 1
                               : mp.get(arr[i]) + 1);
        }
 
        for (int i = 0; i < n; i++) {
            if (mp.get(arr[i]) != -1) {
                 
                // Count frequency of each element
                b[i] = mp.get(arr[i]);
                mp.put(arr[i], -1);
            }
        }
 
        // Last index value is maximum
        // frequency of any element
        Arrays.sort(b);
        if (b[n - 1] % 2 == 0) {
            b[n - 1] = b[n - 1] / 2;
        }
        else {
            b[n - 1] = (b[n - 1] + 1) / 2;
        }
         
        // Last index value is possible
        // minimum frequency of 
        // most frequent element
        Arrays.sort(b);
        return b[n - 1];
    }
     
      // Driver Code
    public static void main(String[] args)
    {
        int A[] = { 1, 4, 4, 1, 4, 4 };
        int N = A.length;
 
        // Function call
        System.out.println(minFreq(A, N));
    }
}

Python3

# Python3 code to implement the above approach
 
# Function to minimize frequency of 
# most frequent element
def minFreq(arr, n) :
     
    b = [0] * n;
     
    mp = dict.fromkeys(arr, 0);
     
    for i in range(n) :
         
        if arr[i] in mp :
            mp[arr[i]] +=1;
             
        else :
            mp[arr[i]] = 1;
           
    for i in range(n) :
         
        if (mp[arr[i]] != -1) :
            # Count frequency of each element
            b[i] = mp[arr[i]];
            mp[arr[i]] = -1;
 
    # Last index value is maximum
    # frequency of any element
    b.sort()
         
    if (b[n - 1] % 2 == 0) :
        b[n - 1] = b[n - 1] // 2;
    else :
        b[n - 1] = (b[n - 1] + 1) // 2;
         
    # Last index value is possible
    # minimum frequency of 
    # most frequent element
    b.sort();    
    return b[n - 1];
 
if __name__ == "__main__" :
     
    A = [ 1, 4, 4, 1, 4, 4 ];
    N = len(A);
 
    # Function call
    print(minFreq(A, N));
    
    # This code is contributed by AnkThon

C#

// C# code to implement the approach
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to minimize frequency of
  // most frequent element
  public static int minFreq(int[] arr, int n)
  {
 
    int[] b = new int[n];
    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.Add(arr[i], 1);
    }
 
    for (int i = 0; i < n; i++) {
      if (mp[arr[i]] != -1) {
 
        // Count frequency of each element
        b[i] = mp[arr[i]];
        mp[arr[i]] = -1;
      }
    }
 
    // Last index value is maximum
    // frequency of any element
    Array.Sort(b);
    if (b[n - 1] % 2 == 0) {
      b[n - 1] = b[n - 1] / 2;
    }
    else {
      b[n - 1] = (b[n - 1] + 1) / 2;
    }
 
    // Last index value is possible
    // minimum frequency of
    // most frequent element
    Array.Sort(b);
    return b[n - 1];
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int[] A = { 1, 4, 4, 1, 4, 4 };
    int N = A.Length;
 
    // Function call
    Console.WriteLine(minFreq(A, N));
  }
}
 
// This code is contributed by ukasp.

Javascript

<script>
// Javascript code to implement the approach
 
// Function to minimize frequency of 
// most frequent element
function minFreq(arr, n) {
 
    let b = new Array(n).fill(0);
    let mp = new Map();
    for (let i = 0; i < n; i++) {
        if (mp.has(arr[i])) {
            mp.set(arr[i], mp.get(arr[i]) + 1)
        } else {
            mp.set(arr[i], 1)
        }
    }
 
    for (let i = 0; i < n; i++) {
        if (mp.get(arr[i]) != -1) {
 
            // Count frequency of each element
            b[i] = mp.get(arr[i]);
            mp.set(arr[i], -1);
        }
    }
 
    // Last index value is maximum
    // frequency of any element
    b.sort((a, b) => a - b);
    if (b[n - 1] % 2 == 0) {
        b[n - 1] = Math.floor(b[n - 1] / 2);
    }
    else {
        b[n - 1] = Math.floor((b[n - 1] + 1) / 2);
    }
 
    // Last index value is possible
    // minimum frequency of 
    // most frequent element
    b.sort((a, b) => a - b);
    return b[n - 1];
}
 
// Driver Code
 
let A = [1, 4, 4, 1, 4, 4];
let N = A.length;
 
// Function call
document.write(minFreq(A, N));
 
// This code is contributed by saurabh_jaiswal.
</script>

Output

Time Complexity: O(N * logN) //the inbuilt sort function takes N log N time to complete all operations, hence the overall time taken by the algorithm is N log N
Auxiliary Space: O(N) // an extra array is used and in the worst case all elements will be stored inside it the hence algorithm takes up linear space

Minimize the maximum frequency of Array elements by replacing them only once

C++

Java

Python3

C#

Javascript

Contact Us