Product of all ints in array besides that an index i

I'm looking for a better implementation of the algorithm.

/*
* You have an ordered array X of n integers. Find the array M containing
* elements where Mi is the product of all integers in X except for Xi.
* You may not use division. You can use extra memory.
*/

#include <iostream>
#include <stack>
#include <queue>
#include <vector>

/*!
* Class used to generate sequences with helper function
*/
template <class T>
class sequence : public std::iterator<std::forward_iterator_tag, T>
{
T val;
public:
sequence(T init) : val(init) {}
T operator *() { return val; }
sequence &operator++() { ++val; return *this; }
bool operator!=(sequence const &other) { return val != other.val; }
};

template <class T>
sequence<T> gen_seq(T const &val) {
return sequence<T>(val);
}

static const int N = 3;
std::stack<int> stk;
std::queue<int> que;
int main(int argc, char *argv[]) {
std::vector<int> seq(gen_seq(1), gen_seq(N + 1));
for (int x = 0, y = N - 1; x < N && y >= 0; ++x, --y) {
if (x == 0 && y == N - 1) {
stk.push(1);
que.push(1);
} else {
stk.push(stk.top() * seq[x - 1]);
que.push(que.back() * seq[y + 1]);
}
}
for (int x = 0; x < N; ++x) {
std::cout << (stk.top() * que.front()) << std::endl;
stk.pop();
que.pop();
}
}


First, some comments on the existing code:

/*
* You have an ordered array X of n integers. Find the array M containing
* elements where Mi is the product of all integers in X except for Xi.
* You may not use division. You can use extra memory
*/


You don't have anything called X in the code, or generate M, so this comment could be better

static const int N = 3;
std::stack<int> stk;
std::queue<int> que;


Why use globals? Also, try to name variables by what they do or represent, rather than their type.

int main(int argc, char *argv[]) {


For that matter, why put the logic in main where you can't test it? I would hope to see something structured like:

std::vector<int> products(std::vector<int> const &X)
{
auto n = X.size();
std::vector<int> M(n, 1);

// ... algorithm ...

return M;
}

int main()
{
static const int N = 3;
std::vector<int> seq(gen_seq(1), gen_seq(N + 1))
std::vector<int> result = products(seq);
// print the result
// or assert correctness
}


Or possibly several test functions, each called from main.

As for the algorithm itself, its working isn't really clear, and that's where comments would be useful. I'm sure you have a deep intuitive understanding of why your nameless stack and queue generate the right results, but without a lot of effort I don't. In six months' time, you may not either.

  for (int x = 0, y = N - 1; x < N && y >= 0; ++x, --y) {
if (x == 0 && y == N - 1) {
stk.push(1);
que.push(1);
} else {
stk.push(stk.top() * seq[x - 1]);
que.push(que.back() * seq[y + 1]);
}
}


we can:

1. move the special case if (x == 0 ... outside
2. then, you only have to iterate over the values used in the second branch (so 1 <= x < N, N-2 >= y >= 0)
3. but we only use x-1 and y+1 in the body of the loop, so simplify this to 0 <= x < N-1 and N-1 >= y >= 0 and just use x and y in the body
4. notice that the two conditions (x < N-1 && y >= 0) will always agree, so we don't have to test both

to get:

  stk.push(1);
que.push(1);
for (int x = 0, y = N-1; x < N-1; ++x, --y)
{
stk.push(stk.top() * seq[x]);
que.push(que.back() * seq[y]);
}


and a simpler implementation:

std::vector<int> products(std::vector<int> const &X)
{
auto n = X.size();
std::vector<int> M(n, 1); // initialise all values to 1

for (int i = 0; i < n; ++i)
{
// set Mj <= Mj * Xi for all j != i
for (int j = 0; j < n; ++j)
if (j != i) M[j] *= X[i];
}
return M;
}


This one uses no extra memory but is O(n^2)

• Thanks for the tips. Though the O(n^2) algorithm is what I was trying to get away from. It is clear, but for very large data sets it is not efficient. Apr 13, 2012 at 20:08

At least IMO, this can be solved quite a bit more cleanly than the examples above show. The "trick" to solving the problem efficiently is to produce running products, starting from both the left and the right side of the input array. To keep some of the later code simple, it's easiest to append a 1 to the beginning of one of those, and the end of the other.

For example, given an input like: [2, 3, 5, 7] we'd produce intermediate results like:

X             2    3    5     7
left          1    2    6    30    210
right    210  105  35   7     1


Just to be sure we're clear, the left holds running products starting from the left--the first item is a 1 we put there "artificially". The second is 1*2. The third is 1*2*3. The fourth is 1*2*3*5, and the last is 1*2*3*5*7.

In right is pretty much the same, except that it's starting from the right instead of the left. So, the first item (starting from the right) is (again) the 1 we insert. Then 1*7, 1*7*5, 1*7*5*3, and 1*7*5*3*2.

Now, to compute each result, we multiply an item in left by an item in right. As I've lined things up in the table above, the items from left and right that are verticall aligned are multiplied to produce each result (and the last item of left and first item of right are simply ignored).

Translating that into C++, we get something like this:

#include <iostream>
#include <deque>
#include <algorithm>
#include <iterator>

int main() {
std::deque<int> X{2, 3, 5, 7};

std::deque<int> left;
std::deque<int> right;

left.push_back(1);

int temp = 1;

std::transform(X.begin(), X.end(), std::back_inserter(left),
[&temp](int i) { temp *= i; return temp; });

temp = 1;

std::transform(X.rbegin(), X.rend(), std::front_inserter(right),
[&temp](int i) { temp *= i; return temp; });

right.push_back(1);

std::transform(left.begin(), left.end()-1,
right.begin()+1,
std::ostream_iterator<int>(std::cout, "\t"),
[](int i, int j) { return i * j; });
}


That produces the following result:

105     70      42      30


Given $N$ inputs, this uses $O(N)$ extra space for right and left, and $O(N)$ time complexity (three traversals of $N$ items each).

Right now, this code uses + on one of the iterators and - on another, limiting the iterators to random access. If desired, it would be fairly trivial to use std::advance (or just ++ and --) to increment the iterators without the requirement for random access. On the other hand, there seems to be little gain from doing so--in theory it would allow us to use (for example) linked lists instead of deques, but that seems unlikely to provide any real advantage.

If you were going to process large collections, you'd have another serious problem: the numbers involved would quick grow much larger than a long or even long long could accommodate. If the collection was very large at all, you'd probably need to use some sort of big integer type to represent the product.