 # EQDIS - Editorial

Testers: Jeevan Jyot Singh, Hriday
Editorialist: Nishank Suresh

1288

None

# PROBLEM:

Given an array A of length N, decide whether it can be partitioned into two arrays B and C that have an equal number of distinct elements.

# EXPLANATION:

The answer is “No” if and only if N is odd and all the elements of A are distinct.

Proof

Let N be odd and all the elements of A be distinct. Then, no matter how the partition is done, B and C will have different sizes (and their number of distinct elements equals their size, so equality is impossible).

Now we have to prove that a suitable division always exists in the other case.

• Suppose A has an even number of distinct elements — for convenience, let’s call them 1, 2, 3, \ldots, 2K. Then, put all occurrences of 1, 2, \ldots, K into B and all occurrences of K+1, K+2, \ldots, 2K into C. B and C now have K distinct elements each, as required.
• Suppose A has an odd number of distinct elements — let them be 1, 2, \ldots, 2K+1. Note that, in particular, 2K+1 \lt N, so some element occurs greater than once — let one such element be x.
Now, create B and C as in the even case by assigning all elements other than x. Finally, place one copy of x in B and the others in C. B and C both have K+1 distinct elements now.

This completes the proof.

Checking the above condition can easily be done with a frequency table in \mathcal{O}(N) since the array elements are \leq N.

# TIME COMPLEXITY

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

# CODE:

Setter's code (C++)
#include<bits/stdc++.h>
using namespace std;

int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
a[x - 1]++;
}
if (n % 2 == 1 && *max_element(a.begin(), a.end()) == 1) {
cout << "NO\n";
} else {
cout << "YES\n";
}
}
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
distinct = len(set(a))
print('yes' if (distinct%2 == 0 or distinct < n) else 'no')

3 Likes
1. if distinct elements are even then no worries they will divide
2. if odd only one element with frequency > 1 is needed to satisfy
void solve(){
int n;
cin>>n;
vi arr(n);
repi(0,n-1) cin>>arr[i];

map<int,int> m;
repi(0,n-1) m[arr[i]]++;

if((int)m.size()==1){
auto it = (*m.begin()).first;
if(m[it] <= 1){
cout<<"NO\n";
return;
}
}else{
int size = m.size();
if(size%2 != 0){
bool check = false;
for(auto x : m){
if(x.second > 1){
check = true;
break;
}
}
if(!check){
cout<<"NO\n";
return;
}
}
}
cout<<"YES\n";
}


What if we take n=4
And array elements 1 1 1 3 ??

1 Like

one array will contain 3 the other will contain 111

Thanks now I got it
I thinks that we should divide the array into B and C with equal no of elements

1 Like

This is my code but it passes only one tc does any one have any edge cases where it fails?

edit: so basically if even it will some how form so even == yes
and if odd then also will form eg 2 3 1 1 1 = 1 2 and 3 1 and will form only exception if all the numbers are unique

#include

#include

#include

#include

#include

using namespace std;

#define ll long long int

int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);      //this is fast I/O (inputput output) use header file <cstdio>

ll t;cin>>t;

while(t--){

ll n; cin>>n;

ll a[n];

map<ll,ll>freq;

for(int i=0; i<n; i++){

cin>>a[i];

freq[a[i]]++;

}

if(n%2!=0)

cout<<"NO"<<endl;

else{

ll unique = 0, odd=0;

for(auto it:freq){

if(it.second==1)

unique++;

else if(it.second%2!=0)

odd++;

}

if((unique+odd)%2==0)

cout<<"YES"<<endl;

else

cout<<"NO"<<endl;

}

}

return 0;


}

What you’re saying is correct, but that isn’t what your code is doing.

if (n%2 == 0) cout << "NO" << endl; is obviously wrong, even on the example you provided.

Try to simplify your code and implement exactly the things you said, and you will get AC:

• If all the numbers are distinct and the array size is odd, the answer is no
• Otherwise the answer is yes
1 Like

plz explain how 1 2 1 can be divide into two parts such that each part has same n.o of distinct elements…

b=11 = 1ele
c=2 = 1ele

/* 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
{
// your code goes here
Scanner sc = new Scanner(System.in);
int tc = sc.nextInt();
while(tc-- > 0){
int n = sc.nextInt();
int []arr = new int[n];
Set<Integer> set = new HashSet<>();
int count = 1;
boolean flag = false;
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();

if(map.containsKey(arr[i])){
map.put(arr[i], map.get(arr[i]  + 1));
if(!flag){
count++;
flag = true;
}
} else{
map.put(arr[i], 1);
}
}

// if there are Even Distinct Elements then they will divide
if(set.size()%2 == 0){
System.out.println("YES");
}else{

// In Case of Odd Distinct Elements one Elements with freq > 1 is required
if(count > 1){
System.out.println("YES");
}else{
System.out.println("NO");
}
}

}
}
}


oh I thought order has to stay same…ok thanks anyway

1 Like