CRCTEAM-Editorial

editorial
, , ,
1

PROBLEM LINK:

CRCTEAM

Author: aniket_111
Tester: sahoomirnalin
Editorialist: aniket_111

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Basic mathematics, divisors, array.

PROBLEM:

Our Chef is hosting a cooking competition in which only two teams can compete at the same time. Both sides should have an equal number of participants to make the competition engaging and fair. Chef was given the duty of forming the two teams as an organizer. There are various conditions for forming teams. He will be assigned a number ‘N’ for each competition, and for each divisor ‘D’ of ‘N’ (including 1 and ‘N’ itself), he will add a member: 1) If ‘D’ is even, go to the first team. 2) if ‘D’ is odd, go to the second team. Chef needs your assistance with the event planning because he is quite busy. Your job is to advise the chef whether or not he can make two teams with the same amount of members.

For Example: For ‘N’ = 10, The divisors are: 1, 2, 5, 10. The first team will have two members corresponding to even divisors 2 and 10. The second team will have two members corresponding to odd divisors 1 and 5. So, in this case, Chef can make two teams.

EXPLANATION

Traverse from 1 to n. Then check if D is a divisor of n.
If yes then check if it is divisble by 2 to get to know whether the divisor is odd or even.
Increase the odd and even counts accordingly.

 if(n % i == 0){
            if(i % 2 == 0)
                even_count++;
            else
                odd_count++;
            }

At last check if both counts are equal. if yes then output should be 1 else 0.
if(even_count == odd_count)
return true;

TIME COMPLEXITY

Time complexity is O(n) per test case

SOLUTIONS:

#include <iostream>

using namespace std;

bool isPossible(int n){
    int odd_count = 0, even_count = 0;
    for(int i=1;i<=n;i++){
        if(n % i == 0){
            if(i % 2 == 0)
                even_count++;
            else{
                odd_count++;
            }
        }
    }
    if(even_count == odd_count)
        return true;
    return false;
}

int main(){
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        if(isPossible(n))
            cout<<1<<endl;
        else cout<<0<<endl;
    }
    return 0;
}