# How to find divisor to maximise remainder?

0x6773

Given two numbers `n` and `k`, find `x`, `1 <= x <= k` that maximises the remainder `n % x`.

For example, n = 20 and k = 10 the solution is x = 7 because the remainder 20 % 7 = 6 is maximum.

My solution to this is :

``````int n, k;
cin >> n >> k;
int max = 0;
for(int i = 1; i <= k; ++i)
{
int xx = n - (n / i) * i; // or int xx = n % i;
if(max < xx)
max = xx;
}
cout << max << endl;
``````

But my solution is `O(k)`. Is there any more efficient solution to this?

TheGreatContini

Not asymptotically faster, but faster, simply by going backwards and stopping when you know that you cannot do better.

Assume `k` is less than `n` (otherwise just output `k`).

``````int max = 0;
for(int i = k; i > 0 ; --i)
{
int xx = n - (n / i) * i; // or int xx = n % i;
if(max < xx)
max = xx;
if (i < max)
break;   // all remaining values will be smaller than max, so break out!
}
cout << max << endl;
``````

(This can be further improved by doing the for loop as long as `i > max`, thus eliminating one conditional statement, but I wrote it this way to make it more obvious)

Also, check Garey and Johnson's Computers and Intractability book to make sure this is not NP-Complete (I am sure I remember some problem in that book that looks a lot like this). I'd do that before investing too much effort on trying to come up with better solutions.

Collected from the Internet

edited at