Dada una matriz de números, devuelve la matriz 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 otros la resolverían. Me siento más cómodo con Java, pero las soluciones en otros idiomas son bienvenidas.

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]

Debe hacer esto O(N)sin usar la división.

Una explicación del método polygenelubricants 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,  }

Ambos 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];
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 necesita estar O (1) en el espacio también, puede hacerlo (lo cual es menos claro en mi humilde opinión)

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

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

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

Aquí hay una pequeña función recursiva (en C ++) para hacer la modificación en su lugar. Sin embargo, requiere O (n) espacio extra (en la pila). Suponiendo que la matriz está en ay N tiene 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;
}

Aquí está mi intento de resolverlo en Java. Disculpas por el formato no estándar, pero el código tiene mucha duplicación, y esto es lo mejor que puedo hacer para que sea legible.

import java.util.Arrays;

public class Products {
    static int[] products(int... nums) {
        final int N = nums.length;
        int[] prods = new int[N];
        Arrays.fill(prods, 1);
        for (int
           i = 0, pi = 1    ,  j = N-1, pj = 1  ;
           (i < N)         && (j >= 0)          ;
           pi *= nums[i++]  ,  pj *= nums[j--]  )
        {
           prods[i] *= pi   ;  prods[j] *= pj   ;
        }
        return prods;
    }
    public static void main(String[] args) {
        System.out.println(
            Arrays.toString(products(1, 2, 3, 4, 5))
        ); // prints "[120, 60, 40, 30, 24]"
    }
}

Los invariantes de bucle son pi = nums[0] * nums[1] *.. nums[i-1]y pj = nums[N-1] * nums[N-2] *.. nums[j+1]. La iparte de la izquierda es la lógica del "prefijo", y la jparte de la derecha es la lógica del "sufijo".

One-liner recursivo

Jasmeet dio una (¡hermosa!) Solución recursiva; Lo he convertido en este (¡horrible!) Java de una sola línea. Realiza modificaciones en el lugar , con O(N)espacio temporal en la pila.

static int multiply(int[] nums, int p, int n) {
    return (n == nums.length) ? 1
      : nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1))
          + 0*(nums[n] *= p);
}

int[] arr = {1,2,3,4,5};
multiply(arr, 1, 0);
System.out.println(Arrays.toString(arr));
// prints "[120, 60, 40, 30, 24]"

Traduciendo la solución de Michael Anderson a Haskell:

otherProducts xs = zipWith (*) below above

     where below = scanl (*) 1 $ init xs

           above = tail $ scanr (*) 1 xs

Eludiendo furtivamente la regla de "sin divisiones":

sum = 0.0
for i in range(a):
  sum += log(a[i])

for i in range(a):
  output[i] = exp(sum - log(a[i]))

Aquí tienes, solución simple y limpia con complejidad O (N):

int[] a = {1,2,3,4,5};
    int[] r = new int[a.length];
    int x = 1;
    r[0] = 1;
    for (int i=1;i<a.length;i++){
        r[i]=r[i-1]*a[i-1];
    }
    for (int i=a.length-1;i>0;i--){
        x=x*a[i];
        r[i-1]=x*r[i-1];
    }
    for (int i=0;i<r.length;i++){
        System.out.println(r[i]);
    }

C ++, O (n):

long long prod = accumulate(in.begin(), in.end(), 1LL, multiplies<int>());
transform(in.begin(), in.end(), back_inserter(res),
          bind1st(divides<long long>(), prod));

1. Viaje a la izquierda-> derecha y siga guardando productos. Llámalo pasado. -> O (n)
2. Viaje a la derecha -> izquierda, mantenga el producto. Llámalo futuro. -> O (n)
3. Resultado [i] = Pasado [i-1] * futuro [i + 1] -> O (n)
4. Pasado [-1] = 1; y Futuro [n + 1] = 1;

En)

Aquí está mi solución en C ++ moderno. Hace uso de std::transformy es bastante fácil de recordar.

Código en línea (wandbox).

#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;

vector<int>& multiply_up(vector<int>& v){
    v.insert(v.begin(),1);
    transform(v.begin()+1, v.end()
             ,v.begin()
             ,v.begin()+1
             ,[](auto const& a, auto const& b) { return b*a; }
             );
    v.pop_back();
    return v;
}

int main() {
    vector<int> v = {1,2,3,4,5};
    auto vr = v;

    reverse(vr.begin(),vr.end());
    multiply_up(v);
    multiply_up(vr);
    reverse(vr.begin(),vr.end());

    transform(v.begin(),v.end()
             ,vr.begin()
             ,v.begin()
             ,[](auto const& a, auto const& b) { return b*a; }
             );

    for(auto& i: v) cout << i << " "; 
}

Esto es O (n ^ 2) pero f # es muuuy hermoso:

List.fold (fun seed i -> List.mapi (fun j x -> if i=j+1 then x else x*i) seed) 
          [1;1;1;1;1]
          [1..5]

Precalcule el producto de los números a la izquierda y a la derecha de cada elemento. Para cada elemento, el valor deseado es el producto de los productos de sus vecinos.

#include <stdio.h>

unsigned array[5] = { 1,2,3,4,5};

int main(void)
{
unsigned idx;

unsigned left[5]
        , right[5];
left[0] = 1;
right[4] = 1;

        /* calculate products of numbers to the left of [idx] */
for (idx=1; idx < 5; idx++) {
        left[idx] = left[idx-1] * array[idx-1];
        }

        /* calculate products of numbers to the right of [idx] */
for (idx=4; idx-- > 0; ) {
        right[idx] = right[idx+1] * array[idx+1];
        }

for (idx=0; idx <5 ; idx++) {
        printf("[%u] Product(%u*%u) = %u\n"
                , idx, left[idx] , right[idx]  , left[idx] * right[idx]  );
        }

return 0;
}

Resultado:

$ ./a.out
[0] Product(1*120) = 120
[1] Product(1*60) = 60
[2] Product(2*20) = 40
[3] Product(6*5) = 30
[4] Product(24*1) = 24

(ACTUALIZACIÓN: ahora miro más de cerca, esto usa el mismo método que Michael Anderson, Daniel Migowski y polygenelubricants arriba)

Difícil:

Use lo siguiente:

public int[] calc(int[] params) {

int[] left = new int[n-1]
in[] right = new int[n-1]

int fac1 = 1;
int fac2 = 1;
for( int i=0; i<n; i++ ) {
    fac1 = fac1 * params[i];
    fac2 = fac2 * params[n-i];
    left[i] = fac1;
    right[i] = fac2; 
}
fac = 1;

int[] results = new int[n];
for( int i=0; i<n; i++ ) {
    results[i] = left[i] * right[i];
}

Sí, estoy seguro de que me perdí algo de i-1 en lugar de i, pero esa es la manera de resolverlo.

También hay una solución no óptima O (N ^ (3/2)) . Sin embargo, es bastante interesante.

Primero preprocese cada multiplicación parcial de tamaño N ^ 0.5 (esto se hace en complejidad de tiempo O (N)). Luego, el cálculo para el múltiplo de otros valores de cada número se puede hacer en 2 * O (N ^ 0.5) tiempo (¿por qué? Porque solo necesita multiplicar los últimos elementos de otros ((N ^ 0.5) - 1) números, y multiplique el resultado con ((N ^ 0.5) - 1) números que pertenecen al grupo del número actual). Al hacer esto para cada número, se puede obtener el tiempo O (N ^ (3/2)).

Ejemplo:

4 6 7 2 3 1 9 5 8

resultados parciales: 4 * 6 * 7 = 168 2 * 3 * 1 = 6 9 * 5 * 8 = 360

Para calcular el valor de 3, uno necesita multiplicar los valores de los otros grupos 168 * 360, y luego con 2 * 1.

public static void main(String[] args) {
    int[] arr = { 1, 2, 3, 4, 5 };
    int[] result = { 1, 1, 1, 1, 1 };
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < i; j++) {
            result[i] *= arr[j];

        }
        for (int k = arr.length - 1; k > i; k--) {
            result[i] *= arr[k];
        }
    }
    for (int i : result) {
        System.out.println(i);
    }
}

Se me ocurrió esta solución y la encontré tan clara ¿qué te parece?

def productify(arr, prod, i):
    if i < len(arr):
            prod.append(arr[i - 1] * prod[i - 1]) if i > 0 else prod.append(1)
            retval = productify(arr, prod, i + 1)
            prod[i] *= retval
            return retval * arr[i]
    return 1

arr = [1, 2, 3, 4, 5] prod = [] productify (arr, prod, 0) print prod

Para completar aquí está el código en Scala:

val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))

Esto imprimirá lo siguiente:

120
60
40
30
24

El programa filtrará el elemento actual (_! = Elem); y multiplique la nueva lista con el método reduceLeft. Creo que esto será O (n) si usa la vista de escala o Iterator para la evaluación diferida.

Basado en la respuesta de Billz: lo siento, no puedo comentar, pero aquí hay una versión scala que maneja correctamente los elementos duplicados en la lista, y probablemente sea O (n):

val list1 = List(1, 7, 3, 3, 4, 4)
val view = list1.view.zipWithIndex map { x => list1.view.patch(x._2, Nil, 1).reduceLeft(_*_)}
view.force

devoluciones:

List(1008, 144, 336, 336, 252, 252)

Agregué mi solución de JavaScript aquí ya que no encontré a nadie sugiriendo esto. ¿Qué es dividir, excepto contar la cantidad de veces que puede extraer un número de otro número? Pasé por calcular el producto de toda la matriz, y luego iterar sobre cada elemento y restar el elemento actual hasta cero:

//No division operation allowed
// keep substracting divisor from dividend, until dividend is zero or less than divisor
function calculateProducsExceptCurrent_NoDivision(input){
  var res = [];
  var totalProduct = 1;
  //calculate the total product
  for(var i = 0; i < input.length; i++){
    totalProduct = totalProduct * input[i];
  }
  //populate the result array by "dividing" each value
  for(var i = 0; i < input.length; i++){
    var timesSubstracted = 0;
    var divisor = input[i];
    var dividend = totalProduct;
    while(divisor <= dividend){
      dividend = dividend - divisor;
      timesSubstracted++;
    }
    res.push(timesSubstracted);
  }
  return res;
}

Estoy acostumbrado a C #:

    public int[] ProductExceptSelf(int[] nums)
    {
        int[] returnArray = new int[nums.Length];
        List<int> auxList = new List<int>();
        int multTotal = 0;

        // If no zeros are contained in the array you only have to calculate it once
        if(!nums.Contains(0))
        {
            multTotal = nums.ToList().Aggregate((a, b) => a * b);

            for (int i = 0; i < nums.Length; i++)
            {
                returnArray[i] = multTotal / nums[i];
            }
        }
        else
        {
            for (int i = 0; i < nums.Length; i++)
            {
                auxList = nums.ToList();
                auxList.RemoveAt(i);
                if (!auxList.Contains(0))
                {
                    returnArray[i] = auxList.Aggregate((a, b) => a * b);
                }
                else
                {
                    returnArray[i] = 0;
                }
            }
        }            

        return returnArray;
    }

Podemos excluir el nums[j](dónde j != i) de la lista primero, luego obtener el producto del resto; Lo siguiente es python waypara resolver este rompecabezas:

from functools import reduce
def products(nums):
    return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ]
print(products([1, 2, 3, 4, 5]))

[out]
[120, 60, 40, 30, 24]

Bueno, esta solución puede considerarse la de C / C ++. Digamos que tenemos una matriz "a" que contiene n elementos como a [n], entonces el pseudocódigo sería el siguiente.

for(j=0;j<n;j++)
  { 
    prod[j]=1;

    for (i=0;i<n;i++)
    {   
        if(i==j)
        continue;  
        else
        prod[j]=prod[j]*a[i];
  }

Una solución más, usando la división. con doble recorrido. Multiplique todos los elementos y luego comience a dividirlo por cada elemento.

{-
Solución recursiva utilizando subconjuntos sqrt (n). Se ejecuta en O (n).

Calcula recursivamente la solución en subconjuntos sqrt (n) de tamaño sqrt (n). 
Luego recurre a la suma del producto de cada subconjunto.
Luego, para cada elemento de cada subconjunto, calcula el producto con
La suma del producto de todos los demás productos.
Luego aplana todos los subconjuntos.

La recurrencia en el tiempo de ejecución es T (n) = sqrt (n) * T (sqrt (n)) + T (sqrt (n)) + n

Suponga que T (n) ≤ cn en O (n).

T (n) = sqrt (n) * T (sqrt (n)) + T (sqrt (n)) + n
    ≤ sqrt (n) * c * sqrt (n) + c * sqrt (n) + n
    ≤ c * n + c * sqrt (n) + n
    ≤ (2c + 1) * n
    ∈ O (n)

Tenga en cuenta que el techo (sqrt (n)) se puede calcular utilizando una búsqueda binaria 
y O (logn) iteraciones, si la instrucción sqrt no está permitida.
-}

Otros productos [] = []
Otros productos [x] = [1]
Otros productos [x, y] = [y, x]
otherProducts a = foldl '(++) [] $ zipWith (\ sp -> map (* p) s) resueltoSubsets subsetOtherProducts
    dónde 
      n = longitud a

      - Tamaño del subconjunto. Requiere que 1 <s <n.
      s = techo $ sqrt $ fromIntegral n

      solvedSubsets = mapear otros subconjuntos de productos
      subsetOtherProducts = otherProducts $ map subconjuntos de productos

      subconjuntos = invertir $ loop a []
          donde loop [] acc = acc
                loop a acc = loop (soltar sa) ((tomar sa): acc)

Aquí está mi código:

int multiply(int a[],int n,int nextproduct,int i)
{
    int prevproduct=1;
    if(i>=n)
        return prevproduct;
    prevproduct=multiply(a,n,nextproduct*a[i],i+1);
    printf(" i=%d > %d\n",i,prevproduct*nextproduct);
    return prevproduct*a[i];
}

int main()
{
    int a[]={2,4,1,3,5};
    multiply(a,5,1,0);
    return 0;
}

Aquí hay un ejemplo ligeramente funcional, usando C #:

            Func<long>[] backwards = new Func<long>[input.Length];
            Func<long>[] forwards = new Func<long>[input.Length];

            for (int i = 0; i < input.Length; ++i)
            {
                var localIndex = i;
                backwards[i] = () => (localIndex > 0 ? backwards[localIndex - 1]() : 1) * input[localIndex];
                forwards[i] = () => (localIndex < input.Length - 1 ? forwards[localIndex + 1]() : 1) * input[localIndex];
            }

            var output = new long[input.Length];
            for (int i = 0; i < input.Length; ++i)
            {
                if (0 == i)
                {
                    output[i] = forwards[i + 1]();
                }
                else if (input.Length - 1 == i)
                {
                    output[i] = backwards[i - 1]();
                }
                else
                {
                    output[i] = forwards[i + 1]() * backwards[i - 1]();
                }
            }

No estoy completamente seguro de que esto sea O (n), debido a la semi-recursión de los Funcs creados, pero mis pruebas parecen indicar que es O (n) a tiempo.

// Esta es la solución recursiva en Java // Llamada de la siguiente manera desde el producto principal (a, 1,0);

public static double product(double[] a, double fwdprod, int index){
    double revprod = 1;
    if (index < a.length){
        revprod = product2(a, fwdprod*a[index], index+1);
        double cur = a[index];
        a[index] = fwdprod * revprod;
        revprod *= cur;
    }
    return revprod;
}

Una solución ordenada con O (n) tiempo de ejecución:

1. Para cada elemento, calcule el producto de todos los elementos que ocurren antes y almacénelo en una matriz "pre".
2. Para cada elemento, calcule el producto de todos los elementos que ocurren después de ese elemento y guárdelo en una matriz "post"

3. Cree un "resultado" de matriz final, para un elemento i,

   result[i] = pre[i-1]*post[i+1];
   

function solution($array)
{
    $result = [];
    foreach($array as $key => $value){
        $copyOfOriginalArray = $array;
        unset($copyOfOriginalArray[$key]);
        $result[$key] = multiplyAllElemets($copyOfOriginalArray);
    }
    return $result;
}

/**
 * multiplies all elements of array
 * @param $array
 * @return int
 */
function multiplyAllElemets($array){
    $result = 1;
    foreach($array as $element){
        $result *= $element;
    }
    return $result;
}

$array = [1, 9, 2, 7];

print_r(solution($array));

Aquí hay otro concepto simple que resuelve el problema O(N).

        int[] arr = new int[] {1, 2, 3, 4, 5};
        int[] outArray = new int[arr.length]; 
        for(int i=0;i<arr.length;i++){
            int res=Arrays.stream(arr).reduce(1, (a, b) -> a * b);
            outArray[i] = res/arr[i];
        }
        System.out.println(Arrays.toString(outArray));

Tengo una solución con O(n)la O(n^2)complejidad de espacio y tiempo que se proporciona a continuación,

public static int[] findEachElementAsProduct1(final int[] arr) {

        int len = arr.length;

//        int[] product = new int[len];
//        Arrays.fill(product, 1);

        int[] product = IntStream.generate(() -> 1).limit(len).toArray();


        for (int i = 0; i < len; i++) {

            for (int j = 0; j < len; j++) {

                if (i == j) {
                    continue;
                }

                product[i] *= arr[j];
            }
        }

        return product;
    }