PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given an integer N, decide whether N has more even divisors then odd divisors or vice versa.
EXPLANATION:
Since the constraints are quite small — N is \leq 100 — it suffices to simply bruteforce over the all the divisors of N to count which of them are even and which are odd.
This is enough get AC - however, there also exists a much faster solution, which requires a bit of casework.
Observe that:
- If N is odd, every divisor of N is also odd; so surely it has more odd divisors than even divisors.
- If N is a multiple of 4, it will always have more even divisors than odd divisors.
- To see why, consider some odd divisor d of N. Since N is a multiple of 4, both 2d and 4d must also divide N.
- So, for each odd divisor of N, we obtain (at least) two even divisors - meaning N has more even than odd divisors.
- If N is even but not a multiple of 4, the number of even and odd divisors will be equal.
This follows from similar logic to the previous case:- For each odd divisor d, 2d will also be a divisor of N which is even.
- For each even divisor d of N, \frac{d}{2} will be an odd divisor of N since N isn’t divisible by 4.
- So, all the divisors of N break up into (even, odd) pairs this way, meaning there’s an equal number of even and odd divisors.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
if n%4 == 0: print(1)
elif n%4 == 2: print(0)
else: print(-1)