Given a number K and a set of sorted numbers. Find if there is any number in the set which divides

Question

Given a number k and a set of sorted numbers. Find if there is any number in the set which divides this number.

For example if k = 8, and set is { 3, 4, 5}, 4 will divide 8. 4 is the answer.

Worst case solution is O(n).

Can we do it better?

Answer 1

How about factorize the number (8 gives us 4 2 1) then search for the factors in your given set? You can use set intersections or bisection search your list of factors. I think it will give you a quicker answer for large sets.

Answer 2

If k is prime, it has no factors in the set and you're done. Otherwise, k = p*q where p is k's smallest factor. Do a binary search for q. If found, you're done. Otherwise, refactor k=p'*q', where p' is the next largest factor of k after p -- if none, you're done. Otherwise, continue the binary search for q' -- note that q' < q, so you can continue the search with the high bound used for q. Continue until a factor is found or you've searched for k's largest factor. This is O(logn). In the concrete case of k = 8, you would search first for 4, then for 2 ... if neither is found then the set does not contain a divisor of k.

EDIT: Hmmm ... I guess this isn't O(logn). If, e.g., the list contained f-1 for every factor f of k, then you would have to search for each f in succession, hitting f-1 each time ... that would be O(n).

Answer 3

Calculate the gcd of k and the product of the members of the set. For the example, gcd(3*4*5,8) = 4.