DISCOOKIE - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Chef has M cookies, and wants to distribute them equally to N kids. Every kid should receive at least one cookie.
In one second, he can create or destroy one cookie. How many seconds does he need?

EXPLANATION:

To distribute the cookies evenly among all the N children, the number of cookies should be a multiple of N.
Chef also needs at least N cookies to ensure that every child receives a cookie.
So, if M \lt N, Chef should create (N-M) more cookies so that he has exactly N, and then distribute them.

When M \geq N, Chef has options: he can either keep creating cookies till he reaches a multiple of N, or keep destroying them till he reaches a multiple.
Let R = (M\bmod N) denote the remainder when M is divided by N.
Then,

  • The minimum number of cookies Chef needs to delete to reach a multiple of N is exactly R.
  • The minimum number of cookies Chef needs to create to reach a multiple of N is exactly (N - R) (or 0, if R = 0).

So, the answer is \min(R, N-R).
In most languages, R can be computed using the % operator as just M % N.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    if m < n: print(n-m)
    else: print(min(m%n, (-m)%n))