Little Elephant and Cards
The Little Elephant loves to play with color cards.
He has n cards, each has exactly two colors (the color of the front side and the color of the back side). Initially, all the cards lay on the table with the front side up. In one move the Little Elephant can turn any card to the other side. The Little Elephant thinks that a set of cards on the table is funny if at least half of the cards have the same color (for each card the color of the upper side is considered).
Help the Little Elephant to find the minimum number of moves needed to make the set of n cards funny.
Input
The first line contains a single integer n (1 ≤ n ≤ 105) — the number of the cards. The following n lines contain the description of all cards, one card per line. The cards are described by a pair of positive integers not exceeding 109 — colors of both sides. The first number in a line is the color of the front of the card, the second one — of the back. The color of the front of the card may coincide with the color of the back of the card.
The numbers in the lines are separated by single spaces.
Output
On a single line print a single integer — the sought minimum number of moves. If it is impossible to make the set funny, print -1.
Sample test(s)
input
3 4 7 4 7 7 4
output
0
input
5 4 7 7 4 2 11 9 7 1 1
output
2
Note
In the first sample there initially are three cards lying with colors 4, 4, 7. Since two of the three cards are of the same color 4, you do not need to change anything, so the answer is 0.
In the second sample, you can turn the first and the fourth cards. After that three of the five cards will be of color 7.
--------------------------------------------editorial---------------------------------------------------------------------------
It is nice to use the map structure in this problem, but you can solve it without map (using sorting and binary serach). Lets iterate through all possible colors that we have and suppose that this currect color is the one that will make our set funny. The minimal number through all this will be the answer. To find the minimal number of turns to make our set funny using current color we need to know two numbers: the number of cards with current color on the front side and the number of cards with the current color on back side (but not at the same time). Let it be integers a and b. Let m = (n + 1) / 2 — the minimal number of the same cards required to get the funny set. Then if a + b < m it is impossible to make set funny using current color at all. If a ≥ m then the answer is 0, otherwise the answer ism - a.
--------------------------------------------------------code---------------------------------------------------------------------
implementation is easy ..
only tricky thing is that there may be possibility a card which is not in front side but , it can made answer. because on opposite side its enough pairs are available ..
------------------------------------------code----------------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define test() int test_case;cin>>test_case;while(test_case--)
#define fr(i,n) for(int i=0;i<n;i++)
#define frr(i,a,n) for(int i=a;i<n;i++)
#define sll(a) scanf("%lld",&a)
#define sl(a) scanf("%ld",&a)
#define si(a) scanf("%i",&a)
#define sd(a) scanf("%ld",&a)
#define sf(a) scanf("%f",&a)
#define rn(a) return a
#define pai pair<int,int>
#define pal pair<li,li>
#define pall pair<lli,lli>
//#define ff first
//#define second second
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define pll(a) printf("%lld\n",a)
#define pl(a) printf("%lld\n",a)
#define pi(a) printf("%d\n",a)
#define pd(a) printf("%lf\n",a)
#define pf(a) printf("%f\n",a)
#define lc (start+end)/2
#define rc lc+1
int main()
{
int n;
cin>>n;
vector<pall> v;
vector<lli> v1;
map<lli,int> back;
set<lli> s;// will contain all distinct colour which can be give answer
for(int i=0;i<n;i++)
{
lli a,b;
cin>>a>>b;
s.insert(a);
s.insert(b);
v.pb(mp(a,b));
v1.pb(a);// it used for applying b'search since not applicable on vector<pair>
if(a!=b)// means there is some card of different colour on opposoit side
// which can be used after swap, eliminate a==b sice if both side card are same
// colour than no meaning of togling
{
back[b]++;
}
}
sort(v.begin(),v.end());
sort(v1.begin(),v1.end());
int mini;
if(n%2==1) mini=n/2+1;
else
mini=n/2;
int ans=INT_MAX;
set<lli> :: iterator its;
for(its=s.begin();its!=s.end();its++)
{
vector<lli> :: iterator it,itv;
lli clr=*its;
itv=lower_bound(v1.begin(),v1.end(),clr);
it=upper_bound(v1.begin(),v1.end(),clr);
int temp=it-v1.begin();
it--;
int cov=it-itv+1;
if(cov>mini)
{
cout<<"0";
return 0;
}
else
{
int req=mini-cov;
if(req<=back[*its])
ans=min(ans,req);
}
}
if(ans!=INT_MAX)
cout<<ans<<endl;
else
cout<<"-1"<<endl;
return 0 ;
}
