EQUALELE - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Testers: wuhudsm, satyam_343
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Frequency arrays

PROBLEM:

Given an array A, in one move you can pick indices i and j and set A_j to b equal to A_i.
Find the minimum number of moves so that all elements of A become equal.

EXPLANATION:

Suppose we perform some operations and make every element equal to x in the end.
Then,

  • x must exist in the original array.
  • If A_i was initially equal to x, then no operation is required on this index.
  • Otherwise, we need exactly one operation to make A_i equal x.

In particular, this means we need exactly N - \text{freq}[x] operations to make everything equal to x, where \text{freq}[x] is the number of occurrences of x in A.

Our aim is to minimize this, so it’s clearly optimal to choose the largest possible value of \text{freq}[x].

This gives us a simple solution: compute the frequency array of A, and let M be its maximum value.
Then, the answer is N - M.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    freq = {}
    for x in a:
        if x in freq: freq[x] += 1
        else: freq[x] = 1
    print(n - max(freq.values()))
2

can anyone tell whats wrong in this code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
unordered_sets;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
s.insert(a[i]);
}
cout<<s.size()-1<<endl;
}
return 0;
}

3

same doubt