Given a ternary array (every element has one the three possible values 1, 2 and 3). Our task is to replace the minimum number of numbers in it so that all the numbers in the array are equal to each other.
Examples:
Input : arr[] = 1 3 2 2 2 1 1 2 3 Output : 5 In this example, frequency of 1 is 3, frequency of 2 is 4 and frequency of 3 is 2. As we can see that 2 is having the more frequency than 1 and 3. So, if we replace all the 1's and 3's by 2 then, the resultant array has all the elements equal to each other in minimum replacements. Here, total no. of 1's and 3's is 5 so it takes 5 replacements to replace them by 2. Hence, the output is 5. Input : arr[] = 3 3 2 2 1 3 Output : 3 In this example, 3 has the max frequency. Hence, minimum number of replacements are 3 to replace 1 and 2 by 3. Hence, the output is 3.
The approach is to calculate frequency of each element of the given array. Then, the difference of n(no. of elements) and max_frequency(frequency of the element occurs maximum time in the array) will be minimum number of replacements needed.
Implementation:
C++
// CPP program minimum number of replacements// needed to be performed to make all the numbers// in the given array equal.#include <bits/stdc++.h>using namespace std;int minReplacements(int arr[], int n){ // Find the most frequent element int freq[3] = { 0 }; for (int i = 0; i < n; i++) freq[arr[i] - 1]++; int max_freq = *max_element(freq, freq + 3); // Returning count of replacing other elements // with the most frequent. return (n - max_freq);}// Driver Functionint main(){ int arr[] = { 1, 3, 2, 2, 2, 1, 1, 2, 3 }; int n = sizeof(arr) / sizeof(arr[0]); cout << minReplacements(arr, n) << endl; return 0;} |
Java
// Java program minimum // number of replacements // needed to be performed // to make all the numbers // in the given array equalimport java .io.*;import java .util.*;class GFG {// Function for // minimum replacementsstatic int minReplacements(int []arr, int n){ // Find the most // frequent element int []freq = new int[3]; for (int i = 0; i < n; i++) freq[arr[i] - 1]++; Arrays.sort(freq); int max_freq = freq[2]; // Returning count of // replacing other elements // with the most frequent return (n - max_freq);}// Driver codestatic public void main (String[] args){ int []arr = {1, 3, 2, 2, 2, 1, 1, 2, 3}; int n = arr.length; System.out.println(minReplacements(arr, n));}}// This code is contributed // by anuj_67. |
Python 3
# Python 3 program minimum number of # replacements needed to be performed # to make all the numbers in the given# array equal.def minReplacements(arr, n): # Find the most frequent element freq = [0] * 3 for i in range(n): freq[arr[i] - 1] += 1 freq.sort() max_freq = freq[2] # Returning count of replacing other # elements with the most frequent. return (n - max_freq)# Driver Codeif __name__ == "__main__": arr = [ 1, 3, 2, 2, 2, 1, 1, 2, 3 ] n = len(arr) print( minReplacements(arr, n) )# This code is contributed # by ChitraNayal |
C#
// C# program minimum number of// replacements needed to be // performed to make all the// numbers in the given array equalusing System;using System.Linq;public class GFG {// Function for minimum replacementsstatic int minReplacements(int []arr, int n){ // Find the most frequent element int []freq = new int[3]; for (int i = 0; i < n; i++) freq[arr[i] - 1]++; int max_freq = freq.Max(); // Returning count of replacing other // elements with the most frequent return (n - max_freq);} // Driver code static public void Main () { int []arr = {1, 3, 2, 2, 2, 1, 1, 2, 3}; int n = arr.Length; Console.WriteLine(minReplacements(arr, n)); }}// This code is contributed by vt_m. |
Javascript
<script> // Javascript program minimum // number of replacements // needed to be performed // to make all the numbers // in the given array equal // Function for // minimum replacements function minReplacements(arr, n) { // Find the most // frequent element let freq = new Array(3); freq.fill(0); for (let i = 0; i < n; i++) freq[arr[i] - 1]++; freq.sort(); let max_freq = freq[2]; // Returning count of // replacing other elements // with the most frequent return (n - max_freq); } let arr = [1, 3, 2, 2, 2, 1, 1, 2, 3]; let n = arr.length; document.write(minReplacements(arr, n));</script> |
Output
5
Time Complexity: O(N)
Auxiliary Space: O(1)
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!