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 
#include 
#include 
#include 

/*!
 * Class used to generate sequences with helper function
 */
template 
class sequence : public std::iterator
{
    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 
sequence gen_seq(T const &val) {
    return sequence(val);
}

static const int N = 3;
std::stack stk;
std::queue que;
int main(int argc, char *argv[]) {
  std::vector seq(gen_seq(1), gen_seq(N + 1));
  for (int x = 0, y = N - 1; x = 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 stk;
std::queue 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 products(std::vector const &X)
{
    auto n = X.size();
    std::vector M(n, 1);

    // ... algorithm ...

    return M;
}

int main()
{
    static const int N = 3;
    std::vector seq(gen_seq(1), gen_seq(N + 1))
    std::vector 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.

Your loop can be cleaner anyway; instead of:

for (int x = 0, y = N - 1; x = 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:

• move the special case if (x == 0 ... outside

• then, you only have to iterate over the values used in the second branch (so 1 = y >= 0)

• but we only use x-1 and y+1 in the body of the loop, so simplify this to 0 = y >= 0 and just use x and y in the body

• notice that the two conditions (x = 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 products(std::vector const &X)
{
    auto n = X.size();
    std::vector 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)

StackExchange Code Review Q#10848, answer score: 6