PETSTORE - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: notsoloud
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

DIFFICULTY:

1126

PREREQUISITES:

None

PROBLEM:

A pet store has N types of animals, the i-th of which has type A_i.

Alice will buy some of these animals and Bob will buy the rest. Is there a way for them to end up with exactly the same multiset of types of animals?

EXPLANATION:

Each type of animal bought by Alice must have a copy that she didn’t buy, so that Bob can buy this copy.

In other words, for a valid split to exist, every type of animal must be present an even number of times.
It’s easy to see that this condition is both necessary and sufficient.

So, all that needs to be done is to check whether each type of animal occurs an even number of times.
One way to do that is as follows:

  • Create an array c of length 100, where c_x denotes the number of times x occurs in A.
    • This is easy to do in \mathcal{O}(N), by simply iterating i from 1 to N and incrementing c_{A_i} by 1 each time.
  • Then, check whether every c_x is even.

Alternately, you can also sort A and check whether A_{2i-1} = A_{2i} (in 1-indexing) for every i.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = sorted(list(map(int, input().split())))
    ans = 'Yes' if n%2 == 0 else 'No'
    for i in range(1, n, 2):
        if a[i] != a[i-1]: ans = 'No'
    print(ans)
1 Like
2

/* 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 s= new Scanner(System.in);
int t=s.nextInt();
while(t–>0)
{
int n=s.nextInt();
int a[] = new int [n];
int temp=0;
for(int i=0;i<n;i++)
{
a[i]=s.nextInt();
temp=temp^a[i];
}
if(temp==0)
System.out.println(“YES”);
else
System.out.println(“NO”);
}
}
}

i have tried another approch by bits xor since every element must repeat even times their xor shld be equal to 0
but my code couldnt pass all test cases it failed at test case 3 can you tell me the reason pls

2 Likes
3

you can’t really count using xor.
101 \oplus 101 = 000 and also 101 \oplus 100 \oplus 001 = 000

2 Likes