Can you please help me solving this one?
You have an unordered array X of n integers. Find the array M containing n elements where Mi is the product of all integers in X except for Xi. You may not use division. You can use extra memory. (Hint: There are solutions faster than O(n^2).)
The basic ones - O(n^2) and one using division is easy. But I just can't get another solution that is faster than O(n^2).
Let left[i] be the product of all elements in X from 1..i. Let right[i] be the product of all elements in X from i..N. You can compute both in O(n) without division in the following way: left[i] = left[i - 1] * X[i] and right[i] = right[i + 1] * X[i];
Now we will compute M: M[i] = left[i - 1] * right[i + 1]
Note: left and right are arrays.
Hope it is clear:)
left and right are meant to be arrays.
left[i] = the product of all elements in X with indices < i and right[i] = the product of all elements in X with indices > i. Then M[i] = left[i] * right[i]. I have described above how to precompute the left and right arrays in linear time.Here's a solution in Python. I did the easy way with division to compare against the hard way without. Do I get the job?
L = [2, 1, 3, 5, 4]
prod = 1
for i in L: prod *= i
easy = map(lambda x: prod/x, L)
print easy
hard = [1]*len(L)
hmm = 1
for i in range(len(L) - 1):
hmm *= L[i]
hard[i + 1] *= hmm
huh = 1
for i in range(len(L) - 1, 0, -1):
huh *= L[i]
hard[i - 1] *= huh
print hard
O(n) - http://nbl.cewit.stonybrook.edu:60128/mediawiki/index.php/TADM2E_3.28
two passes -
int main (int argc, char **argv) {
int array[] = {2, 5, 3, 4};
int fwdprod[] = {1, 1, 1, 1};
int backprod[] = {1, 1, 1, 1};
int mi[] = {1, 1, 1, 1};
int i, n = 4;
for (i=1; i<=n-1; i++) {
fwdprod[i]=fwdprod[i-1]*array[i-1];
}
for (i=n-2; i>=0; i--) {
backprod[i] = backprod[i+1]*array[i+1];
}
for (i=0;i<=n-1;i++) {
mi[i]=fwdprod[i]*backprod[i];
}
return 0;
}
Old but very cool, I've been asked this at an interview myself and seen several solutions since but this is my favorite as taken from http://www.polygenelubricants.com/2010/04/on-all-other-products-no-division.html
static int[] products(int... nums) {
final int N = nums.length;
int[] prods = new int[N];
java.util.Arrays.fill(prods, 1);
for (int // pi----> * <----pj
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 ;
System.out.println("pi up to this point is " + pi + "\n");
System.out.println("pj up to this point is " + pj + "\n");
System.out.println("prods[i]:" + prods[i] + "pros[j]:" + prods[j] + "\n");
}
return prods;
}
Here's what's going on, if you write out prods[i] for all the iterations, you'll see the following being calculated
prods[0], prods[n-1]
prods[1], prods[n-2]
prods[2], prods[n-3]
prods[3], prods[n-4]
.
.
.
prods[n-3], prods[2]
prods[n-2], prods[1]
prods[n-1], prods[0]
so each prods[i] get hit twice, one from the going from head to tail and once from tail to head, and both of these iterations are accumulating the product as they traverse towards the center so it's easy to see we'll get exactly what we need, we just need to be careful and see that it misses the element itself and that's where it gets tricky. the key lies in the
pi *= nums[i++], pj *= nums[j--]
in the for loop conditional itself and not in the body which do not happen until the end of the
iteration. so for
prods[0],
it starts at 1*1 and then pi gets set to 120 after, so prods[0] misses the first elements
prods[1], it's 1 * 120 = 120 and then pi gets set to 120*60 after
so on and so on
O(nlogn) approach:
int multiply(int arr[], int start, int end) {
int mid;
if (start > end) {
return 1;
}
if (start == end) {
return arr[start];
}
mid = (start+end)/2;
return (multiply(arr, start, mid)*multiply(arr, mid+1, end));
}
int compute_mi(int arr[], int i, int n) {
if ((i >= n) || (i < 0)) {
return 0;
}
return (multiply(arr, 0, i-1)*multiply(arr, i+1, n-1));
}
Here is my solution in Python: Easy way but with high computational cost may be?
def product_list(x):
ans = [p for p in range(len(x))]
for i in range(0, len(x)):
a = 1
for j in range(0, len(x)):
if i != j:
a = a*x[j]
ans[i] = a
return ans
