How to find divisor to maximise remainder?

Question

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?

Answer 1

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.

Answer 2

This problem is equivalent to finding maximum of function f(x)=n%x in given range. Let's see how this function looks like:

It is obvious that we could get the maximum sooner if we start with x=k and then decrease x while it makes any sense (until x=max+1). Also this diagram shows that for x larger than sqrt(n) we don't need to decrease x sequentially. Instead we could jump immediately to preceding local maximum.

int maxmod(const int n, int k)
{
    int max = 0;

    while (k > max + 1 && k > 4.0 * std::sqrt(n))
    {
        max = std::max(max, n % k);
        k = std::min(k - 1, 1 + n / (1 + n / k));
    }

    for (; k > max + 1; --k)
        max = std::max(max, n % k);

    return max;
}

Magic constant 4.0 allows to improve performance by decreasing number of iterations of the first (expensive) loop.

Worst case time complexity could be estimated as O(min(k, sqrt(n))). But for large enough k this estimation is probably too pessimistic: we could find maximum much sooner, and if k is significantly greater than sqrt(n) we need only 1 or 2 iterations to find it.

I did some tests to determine how many iterations are needed in the worst case for different values of n:

    n        max.iterations (both/loop1/loop2)
10^1..10^2    11   2   11
10^2..10^3    20   3   20
10^3..10^4    42   5   42
10^4..10^5    94  11   94
10^5..10^6   196  23  196
up to 10^7   379  43  379
up to 10^8   722  83  722
up to 10^9  1269 157 1269

Growth rate is noticeably better than O(sqrt(n)).