[Solved] Pet Store STARTERS 71 CodeChef

Alice and Bob went to a pet store. There are NN animals in the store where the i^{th}ith animal is of type A_iAi​.

Alice decides to buy some of these NN animals. Bob decides that he will buy all the animals left in the store after Alice has made the purchase.

Find out whether it is possible that Alice and Bob end up with exactly same multiset of animals.

Input Format

• The first line of input will contain a single integer TT, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains an integer NN — the number of animals in the store.
  • The next line contains NN space separated integers, denoting the type of each animal.

Output Format

For each test case, output on a new line, YES, if it is possible that Alice and Bob end up with exactly same multiset of animals and NO otherwise.

You may print each character in uppercase or lowercase. For example, the strings YES, yes, Yes, and yES are considered identical.

Constraints

Sample 1:

Input

4
3
4 4 4
4
2 3 3 2
4
1 2 2 3
6
5 5 1 5 1 5

Output

NO
YES
NO
YES

Explanation:

Test case 11: There are 44 possible cases:

• Alice does not buy anything: Bob will buy all the animals and will have 33 animals of type 44.
• Alice buys 11 animal of type 44: Bob will buy the remaining two animals of type 44.
• Alice buys 22 animals of type 44: Bob will buy the remaining one animal of type 44.
• Alice buys all 33 animals of type 44: Bob will not buy anything.

In no case, both Alice and Bob can have the exactly same multiset of pets.

Test case 22: If Alice buys animals 11 and 22, having types 22 and 33 respectively, Bob will buy animals 33 and 44, having types 33 and 22 respectively. Thus, both Alice and Bob have 11 animal of type 22 and 11 animal of type 33.

Test case 33: It can be proven that Alice and Bob cannot have the same multiset of pets in any case.

Test case 44: If Alice buys animals 1, 2,1,2, and 55, having types 5, 5,5,5, and 11 respectively, Bob will buy animals 3, 4,3,4, and 66, having types 1, 5,1,5, and 55 respectively. Thus, both Alice and Bob have 11 animal of type 11 and 22 animals of type 55.

Solution

/* 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 t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
            int[] arr = new int[n];
            for(int i=0;i<n;i++){
                arr[i] = sc.nextInt();
            }
            Arrays.sort(arr);
            int count = 1;
            boolean flag = true;
            for(int i=1;i<n;i++){
                // sauravhathi
                if(arr[i]==arr[i-1]){
                    count++;
                }
                else{
                    if(count%2!=0){
                        flag = false;
                        break;
                    }
                    count = 1;
                }
            }
            if(count%2!=0){
                flag = false;
            }
            if(flag){
                System.out.println("YES");
            }
            else{
                System.out.println("NO");
            }
        }
	}
}

Happy Learning – If you require any further information, feel free to contact me.