Implement a search procedure in terms of a set test procedure Suppose you have a procedure $\mathrm{Prod}(S, t)$ that inputs a finite set of integers&nbsp;$S$ and an integer target&nbsp;$t$, and outputs either “yes” or “no” according to whether there exist distinct elements $x_1, \dots, x_n \in S$ with $\prod_{i=1}^n x_i = t$. You would like to implement an enhanced version of $\mathrm{Prod}(S, t)$, called $\mathrm{ProdSearch}(S, t)$ that outputs the elements $x_1, \dots, x_n$ if such elements exist.

Describe an efficient such procedure $\mathrm{ProdSearch}$ that works by making multiple calls to $\mathrm{Prod}$ as a sub-routine. Carefully explain why your procedure is correct.​
Hint: Suppose you asked your oracle whether there is a subset of $\{x_2,\ldots,x_n\}$ whose product is $t$. What can you deduce if the answer is YES? What can you deduce if the answer is NO?

Here is the full solution:


   If the oracle answers YES, we deduce that we can remove $x_1$ from $S$. If the oracle answers NO, we deduce that every solution must contain $x_1$. We therefore remove $x_1$ from $S$ and update our target product to $t/x_1$. Continuing in this vein for $n-1$ more iterations, we find a solution. This requires at most $n$ calls to $\mathsf{Prod}$ in total.