I participated in a Codeforces challenge recently, and as part of a solution, I wrote the following helper:
def fun1(n, target):
q, r = divmod(n, target)
if r == 0:
return target, q-1
else:
return r, q
My code failed on one test case I couldn't see (and still can't, since the test cases get cut off), but I've found that a correct solution uses
def fun2(n, target):
q, r = divmod(n, target)
if r == 0:
return target, q-1
else:
return n // (q+1), q
When will these two functions not output the same thing?
rcontains the result ofn % targetwhich is equivalent ton - (n // target) * target.This is different from
n // (q+1)which is equivalent ton // (n // target + 1)There is no reason to expect those to always give the same result.