6
$\begingroup$

Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. The task is as follows:

Given an array $<a_1, \ldots, a_n>$ of fixed-length ints, devise an algorithm which returns a new array $<b_1, \ldots, b_n>$ where each $b_i$ is the product of all $a_j$ with $j \neq i$. That is, each element of the result is the product of all other elements in the original array. Division is not allowed, and the algorithm must run in $O(n)$ time and $O(1)$ additional space.

Example: $<1, 2, 3>$ should be updated to $<2*3, 1*3, 1*2>$.

|cite|improve this question
$\endgroup$
  • $\begingroup$ The idea might be to use catalytic space. You can also check whether Ben-Or and Cleve's Barrington-like Computing Algebraic Formulas Using a Constant Number of Registers is helpful. $\endgroup$ – Yuval Filmus Jan 18 '19 at 17:14
  • $\begingroup$ That is really interesting. I don't have the time right now to look into it in depth, but from first glance at the abstracts: Both papers mention rings, so I wonder whether the solutions they produce would not use division. As far as I understand, the first paper's converted programmes run in $O(n)$ time, which is nice, but they use $O(log(n)$ extra space. So even if the solution didn't use division, the time would be sufficient, but it would still use too much extra space. $\endgroup$ – justinpc Jan 19 '19 at 10:12
  • $\begingroup$ There's something weird about the computational model. You need array elements to be able to hold integers of unbounded size. In that case, we might be able to encode the extra data we need and store it inside those array elements (e.g., to store integer $k$ with $b$-bit metadata $m$, store the value $2^b k + m$ in the array). Is the issue that decoding that value would require division? $\endgroup$ – D.W.♦ Feb 10 '19 at 6:50
  • $\begingroup$ That is a good idea, but I will have to move the goalposts a bit. The question requires ints. You could do what you propose with shifting, which is not specifically disallowed, but I don't think that it would follow the spirit of the question. More importantly, I've just re-read the question, and I've realised that I made a big mistake: You are meant to create a new array while leaving the original intact. I'm not really sure what to do about this. I might ask on meta. Therefore Vince's answer wins with a slight modification. $\endgroup$ – justinpc Feb 10 '19 at 12:20
5
$\begingroup$

A variation of a solution left by a commenter called Vince

Given input $a = <a_1, ..., a_n>$.

  1. Allocate result array $b = <b_1, \ldots, b_n>$. Set $product = 1$.
  2. For $i \in [1, n]$, set $b_i = product$ and set $product = product * a_i$.
  3. Set $product = a_n$. For $i \in [n - 1, 1]$, set $b_i = b_i * product$, and set $product = product * a_i$.
  4. Return the array $<b_1, \ldots, b_n>$.

This solution runs in $O(n)$ time and $O(1)$ space additional to that allocated for the result.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The allocated array has to be allocated in any case, as the question requires a new array in the result. Any space allocated in addition to this must be $O(1)$. It would not make sense to restrict oneself by not using the result array for intermediate results. This is a common technique. See my other answer for the case where we update the input array in-place. $\endgroup$ – justinpc Feb 13 '19 at 7:56
  • 1
    $\begingroup$ Yes, I agree with your argument from that common perspective. Another common perspective is when we have an output device such as a write-only tape or console. $\endgroup$ – John L. Feb 13 '19 at 13:06
  • $\begingroup$ Also a valid point. In the book, there are lots of questions which mention x additional space while also using the result space in the solution. Counting the result space, I can't see any cheaper way of solving this problem in $O(n)$ time. Do you know of one? $\endgroup$ – justinpc Feb 13 '19 at 13:52
  • 1
    $\begingroup$ If logarithm and exponentiation are allowed, where subtraction of logarithms functions as division between the original numbers, then 𝑂(1) working space can be enough. That method can be seen as "cheating" or "clever". If only multiplication is allowed, I believe n-3 working space (excluding bookkeeping space such as those used for indexing) is not enough to store the intermediate result, although I have not been able to prove it yet. $\endgroup$ – John L. Feb 13 '19 at 14:00
  • 1
    $\begingroup$ Good point on logarithms, although at least in C/C++, you would have to compute the log of the product as a double and then subtract the log of each element. This could lead to an inexact result once we exponentiate back. I imagine some sort of symbolic, exact representation of logarithms would necessarily use division by implication. $\endgroup$ – justinpc Feb 13 '19 at 19:30
4
$\begingroup$

My in-place $O(nlogn)$ time, $O(logn)$ additional space solution

Let $a = <a_1, ..., a_n>$.

Define the function $\operatorname{f}(\texttt{start}, \texttt{end}) : \texttt{int}$. $\texttt{start}$ and $\texttt{end}$ define the inclusive start and end indices in $a$. The function returns the product of all elements in the range. $\operatorname{f}(1, n)$ updates $a$ in-place to the desired result.

Define $\texttt{length} = (\texttt{end} - \texttt{start}) + 1$. Run the appropriate of the following alternatives:

  1. If $\texttt{length} = 1$, set $a_{start} = 1$ and return the original $a_{start}$.
  2. If $\texttt{length} = 2$, swap $a_{start}$ and $a_{end}$ and return their product.
  3. If $\texttt{length} > 2$:
    • Set $\texttt{leftEnd} = \operatorname{floor}(\texttt{length} /2)$.
    • Set $\texttt{productLeft} = \operatorname{f}(\texttt{start}, \texttt{leftEnd})$.
    • Set $\texttt{productRight} = \operatorname{f}(\texttt{leftEnd} + 1, \texttt{end})$.
    • For $i \in [\texttt{start}, \texttt{leftEnd}]$, replace $a_i$ with $a_i * \texttt{productRight}$,
    • For $i \in [\texttt{leftEnd} + 1, \texttt{end}]$, replace $a_i$ with $a_i * productLeft$. Return $\texttt{productLeft} * \texttt{productRight}$.

Complexity: At each level of recursion, we call $\operatorname{f}$ once on each half of the input, and then we multiply each half with the product from the other half. This gives $O(nlog(n))$ time. The maximum allocation size at each call level is $O(1)$, and there are $log(n/2)$ levels of recursion, so this means $O(log(n))$ additional space allocation.

|cite|improve this answer
$\endgroup$

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.