CODEWITHSUNDEEP
algorithmmathgreatest-common-divisor
Jack Froster
Jack Froster

Reputation: 79

How to find the highest GCD of 2 numbers such that the 2 numbers are from a given range of numbers?

Problem:

Given an input (lower_bound, upper_bound), calculate:

max{ GCD(X,Y), (X,Y) satisfying lower_bound <= X < Y <= upper_bound }

Examples:

INPUT: lower_bound = 1, upper_bound = 100000
OUTPUT: 50000, obtained with X=50000, Y=100000

INPUT: lower_bound = 3, upper_bound = 4
OUTPUT: 1, obtained with X=3, Y=4

This was in a company's coding round and the brute force method which is basically finding GCD of all possible pairs didn't work.

It worked on sample test cases but timed out on hidden test cases during submission.

It is known that the input lower_bound and upper_bound will always be between 1 and 1000000.

Upvotes: 2

Views: 782

Answers (2)

greybeard
greybeard

Reputation: 2467

Going to use lower and upper (dropping _bound) and gcd for GCD(X, Y).
For lower below floor(upper/2), gcd is close to the latter.
For lower close to upper, upper - lower is an upper bound.

from math import sqrt, ceil

def highest_GCD(lower, upper, mess=(__name__ == '__main__')):
    """ Return max{ GCD(X, Y) such that lower <= X < Y <= upper }. """
    # ToDo: useful test cases
    if not 0 < lower < upper:
        return None if not mess else None, 'No GCD for lack of numbers'
    limit = ceil(sqrt(upper))  # one factor got to be smaller
    gap = upper - lower
    candidates = (upper // factor for factor in range(upper // gap, limit)
        ) if limit < gap else range(gap, 0, -1)
    for candidate in candidates:
        higher = upper - upper % candidate
        if lower <= higher - candidate:
            return candidate if not mess else (
                candidate, 'highest GCD in [%d, %d] is %d, dividing X=%d, Y=%d' % (
                       lower, upper, candidate, higher - candidate, higher))

(Using v - v%c is just alternative to the f = v // c, f*c Paul Hankin has used.
I don't prefer one over the other. (Or introduce a floor_multiple(n, factor) for a single occurrence.))
(This was in a company's coding round  A real PITA! Or just checking if you bite the bullet and code a quality solution "fast enough until experience suggest otherwise" you fully well know to be dissatisfying in performance.)

Upvotes: 0

Paul Hankin
Paul Hankin

Reputation: 58221

A number X is a possible gcd of two numbers in the range if there's two multiples of X in the range.

So we need to find the largest X such that there's m such that mX >= lower_bound and (m+1)X <= upper_bound.

For a given m, the largest X that satisfies this (if any) is X = floor(upper_bound / (m+1)), if floor(upper_bound/(m+1)) * m >= lower_bound. Note that a larger m will give a smaller X, so we need to find the smallest possible m to find the largest X.

Now we can just try m=1, m=2, and so on until we find an X (which will be largest possible X).

Note that we've sneakily avoided anything to do with gcd: if we find the largest X such that there's two multiples of X in the range, then necessarily those two multiples of X must have gcd X. And we can find the largest such X by finding the smallest m such that mX and (m+1)X are both in the range (and picking the largest such X for that m).

For example:

def findX(lower, upper):
    for m in range(1, lower+1):
        x = upper // (m + 1)
        if x * m >= lower:
            return 'input:%d,%d => %d, obtained with X=%d, Y=%d' % (lower, upper, x, x * m, x * (m+1))

print(findX(3, 4))
print(findX(10000, 10010))
print(findX(50000, 99999))
print(findX(50000, 100000))

Output:

input:3,4 => 1, obtained with X=3, Y=4
input:10000,10010 => 10, obtained with X=10000, Y=10010
input:50000,99999 => 33333, obtained with X=66666, Y=99999
input:50000,100000 => 50000, obtained with X=50000, Y=100000

(note: an earlier edit of this answer used binary search to find m and x. That was wrong because the existence of x for a particular m is not monotonic).

Upvotes: 4

Related Questions