Given the number K and a set of sorted numbers. Find if the set has a number that divides

Question

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

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

In the worst case, the solution is O (n).

Can we make it better?

Answer 1

How about factoring a number (8 gives us 4 2 1), then look for factors in your given set? You can use a set of intersections or halve your list of factors. I think this will give you a faster answer for large sets.

Answer 2

If k is prime, it has no factors in the set, and you are done. Otherwise, k = p * q, where p is the smallest factor. Do a binary search q. If it is found, everything is ready. Otherwise, the refactor k = p '* q', where p 'is the next largest coefficient k after p - if it is not executed, you are done. Otherwise, continue the binary search q '- note that q' <q, so you can continue the search using the high border used for q. Continue until a factor is found, or you are looking for the largest coefficient k. This is O (logn). In the specific case of k = 8, you must first search for 4, then for 2 ... if none are found, then the set does not contain the divisor k.

EDIT: Hmm ... I guess this is not O (logn). If, for example, the list contains f-1 for each coefficient f of k, then you have to search every f in a row, each time hitting f-1 ... it will be O (n).

Answer 3

We calculate gcd k and the product of the elements of the set. For example, gcd (3 * 4 * 5.8) = 4.