Algorithm

  probledm Link : https://www.codechef.com/problems/CNDY 

Problem

Abhi is a salesman. He was given two types of candies, which he is selling in � different cities.

For the prices of the candies to be valid, Abhi's boss laid down the following condition:

  • A given type of candy must have distinct prices in all � cities.

In his excitement, Abhi wrote down the prices of both the candies on the same page and in random order instead of writing them on different pages. Now he is asking for your help to find out if the prices he wrote are valid or not.

More formally, you are given an array � of size 2�. Find out whether it is possible to split � into two arrays, each of length �, such that both arrays consist of distinct elements.

Input Format

  • The first line of input will contain a single integer �, denoting the number of test cases.
  • Each test case consists of two lines of input.
    • The first line of each test case contains one integer �, denoting the number of cities
    • The second line contains 2� space-separated integers �1,�2,…,�2� — the elements of the array �.

Output Format

For each test case output the answer on a new line — Yes if the given array represents a valid list of prices, and No otherwise.

Each letter of the output may be printed in either uppercase or lowercase, i.e, Yes, YES, and yEs will all be treated as equivalent.

Constraints

  • 1≤�≤103
  • 1≤�≤103
  • 1≤��≤109
  • The sum of � over all testcases does not exceed 2⋅103

Sample 1:

Input
 
Output
 
4
3
4 8 4 6 7 3
3
4 8 6 8 7 8
2
2 4 5 3
4
8 7 9 8 4 6 2 8

Yes
No
Yes
No

Explanation:

Test case 1: One valid way of assigning prices is as follows:

  • The first candy can have a price of 4 in city 1, 6 in city 2, and 8 in city 3.
  • The second candy can have a price of 4 in city 1, 3 in city 2, and 7 in city 3.

Since a valid assignment exists, the answer is "Yes".

Test case 2: No valid set of prices exists that could give this array, since 8 would be repeated somewhere.

Test case 3: One way of splitting the prices is [2,5] and [4,3].

Test case 4: No valid set of prices exists that could give this array.

 

Code Examples

#1 Code Example with C Programming

Code - C Programming

#include<stdio.h>

#include < stdbool.h>

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        int a[2 * n];
        int count;
        bool terminate= false;
        for (int i = 0; i  <  2 * n; i++)
        {
            scanf("%d",&a[i]);
        }
        for (int i = 0; i  <  2 * n; i++)
        {
            count=0;
            for (int j = i; j  <  2 * n; j++)
            {
                if(terminate) break;
                if (a[i] == a[j])
                {
                    count++;
                    if (count == 3) 
                    {
                        terminate=true;
                        break;
                    }
                }
            }
            if(terminate) break;
        }
        output:
        if (count < 3)
            printf("Yes\n");
        else
            printf("No\n">;
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4
3
4 8 4 6 7 3
3
4 8 6 8 7 8
2
2 4 5 3
4
8 7 9 8 4 6 2 8

Output

x
–
+
cmd
Yes
No
Yes
No
Advertisements

Demonstration

CodeChef solution CNDY  - Candies Codechef solution in C,C++

Previous
CodeChef solution DOLL - Red Light, Green Light Codechef solution in C,C++
Next
CodeChef solution GCDQ - Gcd Queries Codechef solution in C,C++