PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
A positive integer is imperfect if it’s divisible by either 2 or 5 but not both.
Given an integer N, find the smallest possible difference between N and an imperfect number.
EXPLANATION:
Our goal is essentially to find the closest imperfect number to N.
There are a couple of different ways to solve this problem.
One way is to simply brute force the answer.
Because the input has N \le 100, and it can be observed that 102 is imperfect, we never need to look further than 102.
So, we can simply try all of M = 1, 2, 3, \ldots, 102, check if M is imperfect, and if it is - update the answer with |N - M|.
This is already enough to get AC.
This solution can be further optimized with a bit of observation.
In particular, the answer is surely not more than 2, because in the range [N-2, N+2] there are at least two different even numbers (and so one of them won’t be divisible by 5).
So, it’s enough to check up to two values on either side of N.
It’s further possible to derive some casework:
- If N is already imperfect, the answer is 0.
- If N is divisible by both 2 and 5 (so it’s divisible by 10), the answer is 2 - either N-2 or N+2 will work.
- If N is divisible by neither 2 nor 5, the answer is 1 since N+1 will work.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python3)
for _ in range(int(input())):
n = int(input())
ans = 200
for m in range(2, 103):
if m%10 == 0: continue
if m%2 == 0 or m%5 == 0: ans = min(ans, abs(n - m))
print(ans)