In this HackerEarth Likeable arrays problem solution Bob and Alice are two friends, they have an array A consisting of N integers, A1,A2,A3,…,AN. Alice likes the arrays in which if element Xis present it must have exactly X or zero occurrences. So, Bob has decided to convert this array to an array which Alice likes. To do that, he can perform the following two operations:
- Add an element of any value to array A.
- Remove an element from array A.
Find the minimum number of operations Bob has to perform so that array is liked by Alice.
HackerEarth Likeable arrays problem solution.
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define endl "n"
#define test ll t; cin>>t; while(t--)
typedef long long int ll;
int main() {
FIO;
test
{
ll n,x; cin>>n;
map<ll,ll>mp;
for(int i=0;i<n;i++){
cin>>x;
mp[x]++;
}
ll ans=0;
for(auto it:mp){
if(it.second>=it.first) ans+=(it.second-it.first);
else ans+=min(it.first-it.second,it.second);
}
cout<<ans<<endl;
}
return 0;
}
Second solution
from collections import defaultdict
t = int(input())
while t > 0:
t -= 1
n = int(input())
a = list(map(int, input().split()))
d = defaultdict(lambda: 0)
for x in a:
d[x] += 1
ans = 0
for x, y in d.items():
ans += min(y, abs(x - y))
print(ans)