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

Okay, we want to know divisor that gives maximum remainder;

let n be a number to be divided and i be the divisor.

we are interested to find the maximum remainder when n is divided by i, for all i<n.

we know that, remainder = n - (n/i) * i //equivalent to n%i

If we observe the above equation to get maximum remainder we have to minimize (n/i)*i

minimum of n/i for any i<n is 1.

Note that, n/i == 1, for i<n, if and only if i>n/2

now we have, i>n/2.

The least possible value greater than n/2 is n/2+1.

Therefore, the divisor that gives maximum remainder, i = n/2+1

Here is the code in C++

#include <iostream>

using namespace std;

int maxRemainderDivisor(int n){
    n = n>>1;
    return n+1;
}

int main(){
    int n;
    cin>>n;
    cout<<maxRemainderDivisor(n)<<endl;
    return 0;
}

Time complexity: O(1)

Answer 2

Nice little puzzle!

Starting with the two trivial cases.

for n < k: any x s.t. n < x <= k solves.

for n = k: x = floor(k / 2) + 1 solves.

My attempts.

for n > k:

x = n
while (x > k) {
    x = ceil(n / 2)
}

^---- Did not work.

1. x = floor(float(n) / (floor(float(n) / k) + 1)) + 1
2. x = ceil(float(n) / (floor(float(n) / k) + 1)) - 1

^---- "Close" (whatever that means), but did not work.

My pride inclines me to mention that I was first to utilize the greatest k-bounded harmonic, given by 1.

Solution.

Inline with other answers I simply check harmonics (term courtesy of @ColonelPanic) of n less than k, limiting by the present maximum value (courtesy of @TheGreatContini). This is the best of both worlds and I've tested with random integers between 0 and 10000000 with success.

int maximalModulus(int n, int k) {
    if (n < k) {
        return n;
    }
    else if (n == k) {
        return n % (k / 2 + 1);
    }
    else {
        int max = -1;
        int i = (n / k) + 1;
        int x = 1;
        while (x > max + 1) {
            x = (n / i) + 1;
            if (n%x > max) {
                max = n%x;
            }
            ++i;
        }
        return max;
    }
}

Performance tests: http://cpp.sh/72q6

Sample output:

Average number of loops:
bruteForce: 516
theGreatContini: 242.8
evgenyKluev: 2.28
maximalModulus: 1.36 // My solution

Answer 3

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)).

Answer 4

For k > n the problem is trivial (take x = n+1).

For k < n, think about the graph of remainders n % x. It looks the same for all n: the remainders fall to zero at the harmonics of n: n/2, n/3, n/4, after which they jump up, then smoothly decrease towards the next harmonic.

The solution is the rightmost local maximum below k. As a formula x = n//((n//k)+1)+1 (where // is integer division).

Answer 5

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 6

waves hands around

No value of x which is a factor of n can produce the maximum n%x, since if x is a factor of n then n%x=0.

Therefore, you would like a procedure which avoids considering any x that is a factor of n. But this means you want an easy way to know if x is a factor. If that were possible you would be able to do an easy prime factorization.

Since there is not a known easy way to do prime factorization there cannot be an "easy" way to solve your problem (I don't think you're going to find a single formula, some kind of search will be necessary).

That said, the prime factorization literature has cunning ways of getting factors quickly relative to a naive search, so perhaps it can be leveraged to answer your question.

Answer 7

I'm wrong for sure, but it looks to me that it depends on if n < k or not.

I mean, if n < k, n%(n+1) gives you the maximum, so x = (n+1).

Well, on the other hand, you can start from j = k and go back evaluating n%j until it's equal to n, thus x = j is what you are looking for and you'll get it in max k steps... Too much, is it?