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:
You have N toffees, which must be divided between 3 friends.
Find the minimum possible imbalance of the distribution, i.e. the difference between the maximum and minimum toffees.
EXPLANATION:
If N is a multiple of 3, you can give each friend \frac{N}{3} toffees, which makes the imbalance 0.
If N is not a multiple of 3, it’s obviously impossible to achieve an imbalance of 0.
However, in this case it’s always possible to achieve an imbalance of 1.
A simple strategy to do this is to just distribute toffees cyclically - that is, give one toffee to friend 1, then one toffee to friend 2, then one to friend 3, then go back to friend 1 and repeat.
So, quite simply,
- If N is a multiple of 3, the answer is 0.
- Otherwise, the answer is 1.
Checking whether N is a multiple of 3 can be done using the % operator in most languages.
Alternately, you can use the N \leq 10 constraint to only check whether N equals one of 3, 6, or 9.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
n = int(input())
if n%3 == 0: print(0)
else: print(1)