When will these functions be different?

85 views Asked by At

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?

1

There are 1 answers

0
Alain T. On

r contains the result of n % target which is equivalent to n - (n // target) * target.

This is different from n // (q+1) which is equivalent to n // (n // target + 1)

There is no reason to expect those to always give the same result.