2
$\begingroup$

Given n numbers we need to find(if possible) the least number k in the range [a,b] such that each number is either divisible by k or divides k. Can we find such number k ?

Example: let n=4 and numbers are 1,20,5,2 and range is [8,16]. Ans is k=10 since each number is either divisible by k or divides k.

My observations: k=1 always if a=1. for other cases i thought of taking lcm of given numbers but there is no guarantee that it will lie in given range and also be smallest!!

So can you help me find how to solve this problem??

$\endgroup$
  • $\begingroup$ In this generality, there's no guarantee at all that a solution $k$ even exists. For example, take $n=1$ and the single number $10$ and the range $[21,29]$. $\endgroup$ – Greg Martin Jul 12 '14 at 19:13
  • $\begingroup$ yes there is no guarantee that k will exist but there must be a approach how to check if k exists or not!! and if it exists then find minimum k in the given range. $\endgroup$ – savvi singh Jul 12 '14 at 19:19
  • $\begingroup$ Can you tell us a bit of the background of this problem? Where did you find it? I'm afraid this smells of an attempt to cheat at an Project Euler challenge. $\endgroup$ – Jyrki Lahtonen Jul 12 '14 at 19:45
  • $\begingroup$ @jyrki: I am not into Project euler so i don't know if there is similar kind of problem or not.This problem was given by professor while studying data structures and he told us to think in terms of gcd and lcm and figure it out. So i dont know if there is similar problem to this or exact.!! $\endgroup$ – savvi singh Jul 12 '14 at 19:49
  • $\begingroup$ Ok. Sorry. I apologize. It just sounded a bit unnatural. In particular when you later impose a bound on the range (such constraints are typical of Project Euler). $\endgroup$ – Jyrki Lahtonen Jul 12 '14 at 19:51
1
$\begingroup$

Let $X$ be your list of integers, $X_\ell = \{x \in X \mid x < a\}$ be the list members less than $a$, $X_m = \{x \in X \mid a \leq x \leq b\}$ be the list members in $[a,b]$, and $X_u = \{x \in X \mid x > b\}$ be the list members greater than $b$. If there is a solution, it is divisible by every member of $X_\ell$ and divides every member of $X_u$.

Compute $L = \mathrm{lcm} (X_\ell)$, the least common multiple of the list members less than $a$. If $X_\ell = \varnothing$, see below. If there is a solution, it is divisible by this $L$. We therefore must have $L \leq b$, otherwise no solution exists in the required interval.

Compute $U = \gcd (X_u)$, the greatest common divisor of the list members greater than $b$. If $X_u = \varnothing$, see below. If there is a solution, it divides this $U$. We therefore must have $a \leq U$, otherwise no solution exists in the required interval.

It is possible that one of $X_\ell$ or $X_u$ is empty. It may happen that $X_m$ is also empty.

  • If $X_\ell = X_m = X_u = \varnothing$, then the problem is ill-posed since there is no list of integers.
  • If $X_\ell = X_m = \varnothing$, then the solution is a divisor of $\gcd(X_u)$ that happens to be in $[a,b]$, which can be found (if it exists) using the prime decomposition of that $\gcd$.
  • If $X_u = X_m = \varnothing$, then the solution is a multiple of $\mathrm{lcm}(X_\ell)$ that happens to be in $[a,b]$, which can be found (if it exists) using the prime decomposition of that $\mathrm{lcm}$.
  • If $X_\ell = \varnothing$ and $X_m \neq \varnothing$, then set $L = \gcd{X_m}$.
  • If $X_u = \varnothing$ and $X_m \neq \varnothing$, then set $U = \mathrm{lcm}(X_m)$.

Note that in the latter two cases, these $U$ and $L$ need not be in $[a,b]$ since the bounds specified by $X_m$ are not strict (each $x \in X_m$ could either divide or be divided by the solution, so the $L$ and $U$ constructed in these cases are conservative.)

If we have not already shown that no solution exists or finished the problem by considering prime decompositions of some $\gcd$ or $\mathrm{lcm}$... By the above, if $L \not \mid U$, then no solution exists. Also, if $L \not \mid x $ for some $x \in X_m$ then no solution exists. Further, if $x \not \mid U$ for some $x \in X_m$ then no solution exists.

If all the numbers are small, as in your example, construct the factorization into primes of $R = U/L = \prod_{i=1}^N p_i^{n_i}$ and for each divisor $r$ of this $R$ determine whether $rL$ is a solution. (In a program, this can be done with nested for loops, one per prime with nonzero exponent.) The check is that $a \leq rL \leq b$, and $rL$ is a solution for all of $X_m$. If you make the sorted list of candidate divisors of $R$, drop the list prefix that is too small and the list suffix that is too large, where all this dropping can be done on one pass through the list or while sorting it, this will tend to be a very short list.

If the numbers are not small, this process could take too long. For instance, $U/L > 10^{200}$ and is not easily factored, or the product of all the $n_i$ is larger than a few billion, or $X_m$ is huge... If this is the case, post more information about the ranges of numbers that are actually expected.

Edit: originally did not have "$rL | U$" in the check. Since we are adding factors to $L$ it is no longer guaranteed that $rL | U$. Therefore, we have to check this each time. Also pointed out that the list can be culled in one pass through the list, so is at worst a linear time operation in the size of $\prod_i n_i$.

Re-edit: Over-thought the problem: As constructed, $rL$ always divides $U$, so there is no need to check for this.

Third edit: $X_\ell$ or $X_u$ could be empty... and also $X_m$ empty with one of them.

$\endgroup$
  • $\begingroup$ RANGE WILL BE WITHIN 10^18 $\endgroup$ – savvi singh Jul 12 '14 at 19:34
  • $\begingroup$ Ah... Then all the numbers will be small enough that this will not be slow. (In particular, the product of the $n_i$ will be no worse than a few thousand, which is a very fast range to check by program.) $\endgroup$ – Eric Towers Jul 12 '14 at 19:40
  • $\begingroup$ what if we cannot find L or U then it mean there do not exist a solution?? $\endgroup$ – savvi singh Jul 12 '14 at 20:28
  • $\begingroup$ @savvisingh: Edited. I had thought those would be trivial, but it turns out there is something to do in those cases. $\endgroup$ – Eric Towers Jul 12 '14 at 21:41
  • $\begingroup$ thank you for editing and giving wonderful explanation:) $\endgroup$ – savvi singh Jul 12 '14 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.