Last Updated: 3 Jun, 2021
Ninja Competition
Easy
Asked in company
Our hero Ninja is organizing a coding competition where only two teams can participate simultaneously. To make the competition interesting and fair, both the teams should have an equal number of members. As an organizer, Ninja got the task of making the two teams.
There are some conditions for creating teams. For each competition, he will be given a number ‘N’, and for each divisor ‘D’ of ‘N’ ( including 1 and ‘N’ itself ), he will add a member:
1) to the first team if ‘D’ is even.
2) to the second team if ‘D’ is odd.
Since Ninja is very busy organizing the event, he wants you to help him with the task. Your task is to tell Ninja if he can create two teams with an equal number of members.
For Example:
For ‘N’ = 10,
The divisors are:
1, 2, 5, 10.
The first team will have two members corresponding to divisors 2 and 10.
The second team will have two members corresponding to divisors 1 and 5.
So, in this case, Ninja can make two teams.
Input Format:
The first line contains an integer ‘T’ which denotes the number of test cases to run.
Then the test case follows:
The first and only line of each test case contains an integer ‘N’ denoting the number given to Ninja.
Output Format:
For each test case print ‘true’ if Ninja can make two teams of equal members with the given ‘N’, else print ‘false’.
Output for each test case will be printed in a separate line.
Note:
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
1 <= N <= 10^5
It is guaranteed that the sum of N over all test cases doesn’t exceed 10^5.
Time Limit: 1 sec
Approaches
We will iterate from 1 to ‘N’ and count the number of even divisors and odd divisors. If they are equal, we will return true, else false.
Algorithm:
- Declare two variables, ‘Odd_Count’ and ‘Even_Count’, and initialize them with zero.
- Start iterating from 1 to ‘N’.
- If the current iterator ( say i ) is a divisor of ‘N’ ( N % i == 0 ):
- If ‘i’ is odd, increase the ‘Odd_Count’ by 1.
- If ‘i’ is even, increase the ‘Even_Count’ by 1.
- If ‘Odd_Count’ is equal to ‘Even_Count’, return true, else return false.
We can observe that the divisors of any integer come in pairs. For each divisor ‘D1’ such that 1 <= ‘D1’ <= sqrt(‘N’) , there will be another divisor ‘D2’ = ‘N’ / ‘D1’ such that sqrt(‘N’) <= ‘D2’ <= ‘N’. But we have to be careful when ‘D1’ is equal to ‘D2’. In that case, we will consider ‘D1’ only once.
We will iterate from 1 to sqrt(‘N’). For each divisor of ‘N’, we will also consider the other divisor ‘N’ / ‘i’ and will count the even and odd divisors accordingly.
Algorithm:
- Declare two variables, ‘Odd_Count’ and ‘Even_Count’, and initialize them with zero.
- Start iterating from 1 to sqrt(‘N’).
- If the current iterator ( say ‘i’ ) is a divisor of ‘N’ ( ‘N’ % ‘i’ == 0 ):
- If i is not equal to sqrt(‘N’):
- If ‘i’ is odd, increase the ‘Odd_Count’ by 1.
- If ‘i’ is even, increase the ‘Even_Count’ by 1.
- If ‘N’ / ‘i’ is odd, increase the ‘Odd_Count’ by 1.
- If ‘N’ / ‘i’ is even, increase the ‘Even_Count’ by 1.
- Else:
- If ‘i’ is odd, increase the ‘Odd_Count’ by 1.
- If ‘i’ is even, increase the ‘Even_Count’ by 1.
- If i is not equal to sqrt(‘N’):
- If ‘Odd_Count’ is equal to ‘Even_Count’ return true, else return false.
Observe that all the numbers with equal counts of odd and even integers form an Arithmetic progression with first term 2 and common difference 4. The general term of the AP is 4 * ‘K’ + 2, where ‘K’ >= 0. So we just have to check whether the given integer N is a term of the AP or not.
So if (‘N’ - 2) / 4 is an integer, then N will be a valid term of the AP. To check this, we will just have to check whether the remainder obtained from dividing (‘N’ - 2) by 4 is zero or not.
Algorithm:
- If ( (‘N’-2) % 4 == 0 ) return true.
- Else return false.