1
$\begingroup$

You are given a function $F$, which can take one or more positive integer operands. Let $L=\{a_1,a_2\ldots a_n\}$.

We need to compute the function $F(L)$ using the least number of transformations/steps. Computing $F(L)$ is not the main goal. Computing it in the fastest possible way is the goal.

Following rules are allowed to be applied to this function.

--> If $L$ has only one element say $x$, then the $F(L) = x$;

--> If all elements in $L$ are even then $F(L)=2F(L')$, where $L'$ contains all elements in $L$ divided by 2. For example $F(4,8,10)= 2*F(2,4,5)$

--> If some elements in $L$ are odd and some are even, then $F(L)=F(L')$, where $L'$ has same odd elements as L, but the even elements in $L$ are made odd by removing the factor 2. For example $F(6,9,20)=F(3,9,5)$

--> If any of the integers in the list is 1, then $F(L)=1$;

--> If two or more integers in $a_1,a_2\ldots a_n$ are same, then we can remove the copies and keep only one of them. For example $F(4,5,6,5)=F(4,5,6)$

--> For any pair $a_i$ and $a_j$ where($a_i<a_j$), you can replace $a_j$ with $a_j-a_i$

$F(4,7,8)=F(4,(7-4),8)=F(4,3,8)$


It is easy to notice that this process terminates, because at each step, either the value one of the operands is reduced or the number of operands is reduced.

Given $L$ can there be a DP to optimize the number of operations needed to solve $F$, or is there a greedy strategy that is optimal or constant approximate of the optimal?

For example

Consider the following instance

$F(15,30,45)$

Depending on your choice, you can compute this value in several ways.

\begin{align*} F(15,30,45)& =F(15,30,45-30)=F(15,30,15)\\ & =F(15,30)\\ & =F(15,30-15)=F(15,15)\\ & =F(15)=15 \end{align*}

which takes 4 iterations.

Another way is

\begin{align*} F(15,30,45)& =F(15,30-15,45)=F(15,15,45)\\ & =F(15,45)\\ & =F(15,45-15)=F(15,30)\\ & =F(15,30/2)=F(15,15)\\ & =F(15)=15 \end{align*}

which takes 5 iterations.

I want an algorithm which finds the optimal solution.

$\endgroup$
  • $\begingroup$ If $L=\{2,2k\}$, then exactly $k$ steps are required. Since every problem instance in this family can be encoded in $O(\log k)$ bits, that means any solution that generates a complete sequence of operations takes time at least exponential in the problem size in the worst case. $\endgroup$ – j_random_hacker Dec 12 '18 at 12:02
  • $\begingroup$ Nice observation, Reminds me that I missed another operation. I am adding one special operation now. If $L={a_1,a_2\ldots a_n}$ and all are even, then $F(L)=2F({a_1/2,a_2/2\ldots a_n/2})$ $\endgroup$ – Vk1 Dec 12 '18 at 12:06
  • $\begingroup$ That doesn't improve things for $L=\{3, 3k\}$. $\endgroup$ – j_random_hacker Dec 12 '18 at 12:35
  • 1
    $\begingroup$ It does improve things. case 1:- 3k is even, Then F(L)=F(3,3k/2) case 2:- 3k is odd, then F(L)=F(3,3k-3)=F(3,(3k-3)/2) Now at least one of the operands reduces by half after 2 iterations. $\endgroup$ – Vk1 Dec 12 '18 at 13:47
  • 1
    $\begingroup$ You're right, it's more helpful than I first thought, especially since you can always choose to halve the largest operand in 2 steps. This means that for $n$ integers having maximum value $k$, the time bound is now at most $O(n\log k)$, since each element can be reduced to 1 in at most $2\log_2 k$ steps. $\endgroup$ – j_random_hacker Dec 12 '18 at 14:04
1
$\begingroup$

Yes, there is a simple way to compute $F$.

Proposition: $F(a_1,a_2\ldots a_n)=\gcd (a_1,a_2\ldots a_n)$, where $\gcd$ is the greatest common divisor.

Proof: I will leave it as an exercise. Hint, the replacement of $a_j$ by $a_j-a_i$ whenever $a_i<a_j$ is very powerful.

Here is a simple and efficient algorithm to compute $F(a_1,a_2\ldots a_n)$.

  • Let $r = a_1$.
  • Iterate $i$ through $2,3, \cdots, n$, setting $r$ to $\gcd(a_i, r)$. Here $\gcd(a_i,r)$ can be computed by any of your favorite GCD algorithms such as Euclidean algorithm or binary GCD algorithm.
  • return $r$.
$\endgroup$
  • $\begingroup$ Good observation, it is emulating binary GCD algorithm. I know its computing the gcd. The question is not about what it is trying to compute. The question is to find the optimal way to compute it. More specifically an instance optimal way to compute it. $\endgroup$ – Vk1 Dec 12 '18 at 14:10
  • 1
    $\begingroup$ I would recommend that $F$ be removed from the question. You are talking about how to reach the accept states of $L$ in least number of steps. Once you have mentioned the optimal way to compute it, it becomes rather misleading since the nature explanation of "it" is the value of $F$. Instead, please define $S$(run), the number of steps for a run. Add one to $S$(run) for each step. Do not mention $F$ at all. $\endgroup$ – Apass.Jack Dec 12 '18 at 17:47

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.