PAIREQ - EDITORIAL

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: abhi_inav
Testers: inov_360, iceknight1093
Editorialist: hrishik85

DIFFICULTY:

928

PREREQUISITES:

None

PROBLEM:

Chef has an array A of length N. In one operation, Chef can choose 2 distinct indices i,j and either change Ai to Aj or Aj to Ai. Any number of operations can be carried out. Find the minimum number of operations required to make all the elements of the array equal.

EXPLANATION:

Concept
Each test case has 2 lines of input. Our input acceptance should take this into consideration.
What does the problem actually need us to do? - We need to make all elements equal.

  • If all elements of the array are different, then (N - 1) elements of the array can be converted into any 1 element in (N - 1) operations
  • Suppose some elements of the array are common. In this case, we need to find which element should we convert the entire array into such that we need minimum number of operations

This element will be the element which has the most frequency in the array. Supposed frequency of this element is F, then we need to output (N - F)

Implementation

  • Sort the array in an ascending order
  • Traverse through the array from left to right and maintain a counter which stores the frequency of each unique element
  • Take the maximum value of this counter as F - and then output (N - F)

TIME COMPLEXITY:

Time complexity is O(N logN).

SOLUTION:

Tester's Solution
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(n - max([a.count(x) for x in a]))
Editorialist's Solution
t=int(input())
for _ in range(t):
    n=int(input())
    arr=sorted(list(map(int,input().split())))
    final=1
    count=1
    i=0
    while i<(n-1):
        if arr[i]==arr[i+1]:
            count=count+1
            i=i+1
            if final<count:
                final=count
            continue
        count=1
        i=i+1
    print(n-final)

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

      int getMaxValue(unordered_map<int,int> takeMap){
                int maxValue = 0,maxKeyFromValue;
                for (auto it: takeMap)
                {
                    if (maxValue < it.second)
                    {
                        maxValue = it.second;
                        maxKeyFromValue = it.first;
                    }
                }
                return maxKeyFromValue;
            }

int main() {
// your code goes here
int t;
cin >> t;
while(t–){
int n,counter=0,fixed;
int arr[n];
cin >> n;
unordered_map<int,int> frequency;

    for(int i=0;i<n;i++){
        cin >> arr[i];
        if(frequency.count(arr[i]) == 0){
            frequency[arr[i]] = 1;
        }else if(frequency.count(arr[i]) > 0){
             frequency[arr[i]] += 1;
        }
        
    }

    
    
    fixed = getMaxValue(frequency);
    
    for(int j=0;j<n;j++){

        if(fixed != arr[j]){
            counter ++;
        }
    }
    
    
    cout << counter << endl;
    // cout << fixed  << endl;
}
return 0;

}

I was using the same concept except the (N-F) at the end, where is N is length of array and F is the highest frequency of any integer. I was facing run time error “RE (SIGSEGV)” . Is this because of memory or heaps issue as it was showing 5308kb, is it because the max memory limit for this question is 50kb, is it for that reason the problem was coming?

Time complexity is O(NlogN) as we are sorting the array.

What is wrong with it?

#include
using namespace std;

maxfreq(int arr[],int n)
{
int i,j,maxFreq,countt=0;
for(i=0;i<n;i++)
{
if(arr[0]==arr[i])
countt++;
}
maxFreq=countt;
for(i=1;i<n;i++)
{
countt=0;
for(j=0;j<i;j++)
{
if(arr[i]==arr[j]) break;
}
if(j!=(i-1)||(arr[i]==arr[j]))
continue;

    else
    {
        for(j=i;j<n;j++)
        {
            if(arr[i]==arr[j])
                countt++;
        }
        if(maxFreq<countt)
            maxFreq=countt;
    }
}
return maxFreq;

}

int main()
{
int i,j,t,n;
cin>>t;
for(i=0;i<t;i++)
{
cin>>n;
int arr[n];
for(j=0;j<n;j++)
{
scanf("%d",&arr[j]);
}
cout<<n-maxfreq(arr,n)<<endl;
}
return 0;
}

@lalwalataukir - thanks a lot!. Updated the error.

Below is the Java code for the above explanation.
I have taken a Hashmap, however we can also implement is using another array of same size i.e., frequency array which will store frequency of each element.

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T>0){
		    int N = sc.nextInt();
		    int[] A = new int[N];
		    
		    HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		    for(int i=0; i<N; i++){
		        A[i] = sc.nextInt();
		        
		        if(hm.get(A[i]) == null){
		            hm.put(A[i], 1);
		        }else{
		            hm.put(A[i], hm.get(A[i])+1);
		        }
		    }
		    if(hm.size() == 1)
		        System.out.println(0);
		    else{
		        int maxFrequency = Integer.MIN_VALUE;
		        for(int i=0; i<N; i++){
		            if(hm.get(A[i]) > maxFrequency){
		                maxFrequency = hm.get(A[i]);
		            }
		        }
		        System.out.println(N - maxFrequency);
		    }
		    
		    T--;
		}
	}
}