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

## Comments