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

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

Related Related

HotTag

Archive