Puzzle .. solving product values ​​in array X

Question

Could you help me solve this problem?

You have an unordered array X of n integers. Find an array M containing n elements, where Mi is the product of all integers in X except Xi. You cannot use division. You can use additional memory. (Hint: there are solutions faster than O (n ^ 2).)

The main ones are O (n ^ 2), and one using division is simple. But I just can't get another solution that is faster than O (n ^ 2).

Answer 1

Let left[i] be the product of all elements from X from 1..i . Let right[i] be the product of all elements from X from i..N . You can calculate as O(n) without division as follows: left[i] = left[i - 1] * X[i] and right[i] = right[i + 1] * X[i] ;

Now we calculate M : M[i] = left[i - 1] * right[i + 1]

Note: left and right are arrays.

Hope that is clear :)

Answer 2

Here is a solution in Python. I made an easy way with separation to compare with a hard way without. Am I getting a 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 

Answer 3

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; } 

Answer 4

O(nlogn) :

 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)); } 

Answer 5

Old, but very cool, I was asked about this at an interview and I saw several solutions, 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; } 

This is what happens if you write prods [i] for all iterations, you will see the following calculation

 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] 

therefore, each finger [i] gets hit twice, one from head to tail and once from tail to head, and both these iterations accumulate the product as they move to the center, so it’s easy to see that we get exactly what we need , we just need to be careful and see that it skips the element itself and that where it becomes difficult. the key lies in

 pi *= nums[i++], pj *= nums[j--] 

in a loop cycle condition, and not in a body that does not occur until the end of the iteration. Thus, for prods[0], it starts with 1 * 1, and then pi gets the value 120 after, so prods [0] skips the first elements of prods[1], it 1 * 120 = 120, and then pi is set to 120 * 60 after so on and so forth