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 Function int 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 equal import java .io.*; import java .util.*; class GFG { // Function for // minimum replacements static 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 code static 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 Code if __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 equal using System; using System.Linq; public class GFG { // Function for minimum replacements static 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> |
5
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!