Dada una serie de números, devuelve una serie de productos de todos los demás números (sin división)

Me hicieron esta pregunta en una entrevista de trabajo y me gustaría saber cómo la resolverían otros. Me siento más cómodo con Java, pero se aceptan soluciones en otros lenguajes.

Dada una matriz de números, numsdevuelve una matriz de números products, donde products[i]es el producto de todos nums[j], j != i.
Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
      = [120, 60, 40, 30, 24]
Debes hacer esto O(N)sin usar división.

Apr 21 '10 12:04 polygenelubricants

Una explicación del método de los lubricantes poligénicos es:

El truco consiste en construir las matrices (en el caso de 4 elementos):

{              1,         a[0],    a[0]*a[1],    a[0]*a[1]*a[2],  }
{ a[1]*a[2]*a[3],    a[2]*a[3],         a[3],                 1,  }

Ambas cosas se pueden hacer en O(n) comenzando en los bordes izquierdo y derecho respectivamente.

Luego, multiplicar las dos matrices elemento por elemento da el resultado requerido.

Mi código se vería así:

int a[N] // This is the input
int products_below[N];
int p = 1;
for (int i = 0; i < N; ++i) {
    products_below[i] = p;
    p *= a[i];
}

int products_above[N];
p = 1;
for (int i = N - 1; i >= 0; --i) {
    products_above[i] = p;
    p *= a[i];
}

int products[N]; // This is the result
for (int i = 0; i < N; ++i) {
    products[i] = products_below[i] * products_above[i];
}

Si también necesita que la solución sea O(1) en el espacio, puede hacer esto (que, en mi opinión, es menos claro):

int a[N] // This is the input
int products[N];

// Get the products below the current index
int p = 1;
for (int i = 0; i < N; ++i) {
    products[i] = p;
    p *= a[i];
}

// Get the products above the current index
p = 1;
for (int i = N - 1; i >= 0; --i) {
    products[i] *= p;
    p *= a[i];
}

Apr 21 '2010 06:04 Michael Anderson

Aquí hay una pequeña función recursiva (en C++) para realizar la modificación in situ. Sin embargo, requiere O(n) espacio adicional (en la pila). Suponiendo que la matriz tiene ay Nmantiene la longitud de la matriz, tenemos:

int multiply(int *a, int fwdProduct, int indx) {
    int revProduct = 1;
    if (indx < N) {
       revProduct = multiply(a, fwdProduct*a[indx], indx+1);
       int cur = a[indx];
       a[indx] = fwdProduct * revProduct;
       revProduct *= cur;
    }
    return revProduct;
}

Apr 23 '2010 03:04 Jasmeet