#102 Ahi va mi versión (espero que no quede muy mal al perder la identacion
static int[] GoogleAnswer(int[] a)
{
int[] b = new int[a.Length];
int var1 = 1;
int var2 = 1;
for (int i = 0; i < b.Length; i++) b[i] = 1; //inicializar valores de b a 1
for (int i = 0, j = b.Length-1; i < b.Length; i++, j--)
{
b[i] *= var1;
var1 *= a[i];
b[j] *= var2;
var2 *= a[j];
}
return b;
}
La idea es tener dos variables donde se van acumulando las multiplicaciones, una avanza por la izquierda, otra avanza por la derecha. A cada posición del vector b le corresponde lo que avanzo la variable por la izquierda (sin contarle a el) por lo que avanzo la variable por la derecha).
Es decir, en el bucle, en vez de intentar calcular a cada paso el valor en una posición, calculad el valor de estas variables y multiplicarlo por lo que habia en esa posición en el vector (en realidad, se multiplica primero y luego se calcula var1 y var2 para que excluya el elemento a[i]). Hay que inicializar previamente todos los valores de b a 1.
Yo utilizo i y j, podria usar solo i e ir restandolo de b.length-1, pero queda mas simple usando dos contadores.
En total, tiempo O(n) con cuatro multiplicaciones y asignaciones en cada paso y sin necesitar arrays auxiliares, solo var1 y var2
El codigo funciona (C#)
Sigo buscando a quien me resuelva el como calcular los caracteres comunes de dos cadenas de texto en O(n) (o si lo preferis, elementos comunes en dos arrays de enteros no ordenados (el problema de google no especifica nada, pero ordenados es trivial)
#105#102 Felicitaciones! Versión en python:
def arreglar4(a):
ciclos=0
b=[1 for x in a]
var1 = 1
var2 = 1
....
largo=len(a)
j=largo-1
for i in range(0,largo):
<------>b[i]*=var1
<------>var1*=a[i]
<------>b[j]*=var2
<------>var2*=a[j]
<------>ciclos+=1
<------>j-=1
print b
print ciclos
Procedure trabajarengoogle (var a,b: array of integer ; m,i:integer); begin trabajarengoogle (a, b, m*a[i], i+1); b[i]:= m; end;
El problema no es que la complejidad del problema no sea O(n), sino que lo que contiene cada elemento de la matriz b no es lo que pide le problema: "bi = a1*a2*...*an/ai".
Por ejemplo, en tu propuesta, la primera posición de b tiene el valor 1, la segunda posición tiene a1, la tercera posición tiene a1 * a2, etc...
#109#14 Por cierto, con todo el respeto del mundo, resolveríais eso en matemática discreta con ecuaciones diofánticas, pero eso en mi colegio se llamaba cálcular el minimo común multiplo de 17 y 16 (sumar 1 para la respuesta), y luego a la respuesta la factorizas y el divisor mayor (imagino que eso en Discreta sería un cero, pero recuerda a la EGB)
#111#56 El truco está en ir almacenando los resultados intermedios
a1 * a2
a1 * a2 * a3
...
para no tener que recarculando.
De todas formas que no cuente Google conmigo. Voy a hacer mi propio buscador y se van a enterar. Pondré noticias de Ronaldo, tetas, culos y la crisis y triplicaré las visitas a Google.
blog.seattleinterviewcoach.com/2009/02/140-google-intervi... 
static int[] GoogleAnswer(int[] a)
{
int[] b = new int[a.Length];
int var1 = 1;
int var2 = 1;
for (int i = 0; i < b.Length; i++) b[i] = 1; //inicializar valores de b a 1
for (int i = 0, j = b.Length-1; i < b.Length; i++, j--)
{
b[i] *= var1;
var1 *= a[i];
b[j] *= var2;
var2 *= a[j];
}
return b;
}
La idea es tener dos variables donde se van acumulando las multiplicaciones, una avanza por la izquierda, otra avanza por la derecha. A cada posición del vector b le corresponde lo que avanzo la variable por la izquierda (sin contarle a el) por lo que avanzo la variable por la derecha).
Es decir, en el bucle, en vez de intentar calcular a cada paso el valor en una posición, calculad el valor de estas variables y multiplicarlo por lo que habia en esa posición en el vector (en realidad, se multiplica primero y luego se calcula var1 y var2 para que excluya el elemento a[i]). Hay que inicializar previamente todos los valores de b a 1.
Yo utilizo i y j, podria usar solo i e ir restandolo de b.length-1, pero queda mas simple usando dos contadores.
En total, tiempo O(n) con cuatro multiplicaciones y asignaciones en cada paso y sin necesitar arrays auxiliares, solo var1 y var2
El codigo funciona (C#)
Sigo buscando a quien me resuelva el como calcular los caracteres comunes de dos cadenas de texto en O(n) (o si lo preferis, elementos comunes en dos arrays de enteros no ordenados (el problema de google no especifica nada, pero ordenados es trivial)
from Numeric import *;
a=[2,4,6,8,10]
b=zeros(len(a),Int)
b[0]=1
for i in range (1,len(a)):
b[i]=a[i-1]*b[i-1]
prev=1
for i in range (len(a)-1,
1,1):b[i]=b[i]*prev
prev=prev*a[i]
print a
print b
def arreglar4(a):
ciclos=0
b=[1 for x in a]
var1 = 1
var2 = 1
....
largo=len(a)
j=largo-1
for i in range(0,largo):
<------>b[i]*=var1
<------>var1*=a[i]
<------>b[j]*=var2
<------>var2*=a[j]
<------>ciclos+=1
<------>j-=1
print b
print ciclos
Procedure trabajarengoogle (var a,b: array of integer ; m,i:integer);
begin
trabajarengoogle (a, b, m*a[i], i+1);
b[i]:= m;
end;
El problema no es que la complejidad del problema no sea O(n), sino que lo que contiene cada elemento de la matriz b no es lo que pide le problema: "bi = a1*a2*...*an/ai".
Por ejemplo, en tu propuesta, la primera posición de b tiene el valor 1, la segunda posición tiene a1, la tercera posición tiene a1 * a2, etc...
Pero yo lo he argumentado algo más
No veas que rayada llevamos todos con el problemita de los Coj...googles
a1 * a2
a1 * a2 * a3
...
para no tener que recarculando.
De todas formas que no cuente Google conmigo. Voy a hacer mi propio buscador y se van a enterar. Pondré noticias de Ronaldo, tetas, culos y la crisis y triplicaré las visitas a Google.