EVENODDDIV - Editorial

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)