Interview Question

Senior Software Engineer Interview

-

Google

Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division.

AnswerAdd Tags

Interview Answers

34 Answers

30

It seems to me that for any number array[i], you're looking for PRODUCT(all array[j] where j i]) we can simply precompute these "running products" first from left-to-right, then right-to-left, storing the results in arrays. So, leftProduct[0] = array[0]; for j=1; j = 0; j-- rightProduct[j] = rightProduct[j+1]*array[j]; then to get our answer we just overwrite the original array with the desired product array[0] = rightProduct[1]; array[n-1] = leftProduct[n-2]; for j=1; j < n-1; j++ array[j] = leftProduct[j-1] * rightProduct[j+1] and clearly this solution is O(n) since we just traversed the data 3 times and did a constant amount of work for each cell.

betterStill on

3

betterStill, I think you have the answer the interviewer wanted.. But... if the array is google sized, don't we have to worry about overflows?

Ethelbert on

2

narya trick is good but really useful as it might take more iterations depending on values... eg. 2,3,1000000000000000 so if you have 3 numbers and if you are trying for the first one it will go for 500000000000000 iterations, hence as the overall product value wrt to the value matters a lot... try something else....

kiran on

1

narya, your solution is not O(n). You have to also account for how many times you will run through the inner loop - which will be a lot. You can do it in O(n) time and O(n) space. In one pass, populate B[i] with the product of every number before i. In the second pass, multiply this with the product of every number after i. Can't think of a way to do it without the second array. void ArrayMult(int *A, int size) { runningProduct = 1; int *B = new int[size]; for(int i = 0; i = 0; --i) { B[i] *= runningProduct; runningProduct *= A[i]; } for(int i = 0; i < size; ++i) { A[i] = B[i]; } }

donutello on

1

<strong>Brutefoce Method : </strong> The brute-force method suggests that if we take each element, multiply all elements and store the product in the array B[i], then it would take O(n^2) time. <strong>Other Solution : </strong> The other solution to this problem can be we multiply all the elements of the array "A" and store the product in a variable (say product.), and then divide the product by each element, then we will get the desired array. The C code of the solution can be : #include int main() { int n,i=0; scanf("%d",&n); int arr[n]; int brr[n]; int product = 1; for(i=0;i This solution will take O(n) time. The space complexity of this solution will be O(1). If we have particularly given that "We can't use the *DIVISION* operator, then the solution to this problem will be as follows." polygenelubricants method : Let we have 2 arrays, "A" and "B". Let the length of "A" is 4. i.e. {A[0],A[1],A[2],A[3]} Then we will make two arrays (say temp1 and temp2). One array will be storing the product the array before a particular element and temp2 will store the product of elements after a particular element. temp1 = { 1 , A[0] , A[0]*A[1] , A[0]*A[1]*A[2]} temp2 = {A[1]*A[2]*A[3] , A[2]*A[3] , A[3] , 1} And then we will correspondingly multiply temp1 and temp2 and store in B. B = {A[1]*A[2]*A[3] , A[0*A[2]*A[3] , A[0]*A[1]*A[3] , A[0]*A[1]*A[2]} The C code to this solution will be : #include int main() { int n,i=0; scanf("%d",&n); int A[n],B[n]; int temp1[n], temp2[n]; for(i=0;i=0;i--) { temp2[i] = product; product *= A[i]; } for(i=0;i The time complexity to this solution will be O(n) and the space complexity to this problem will also be O(n).

Ajay on

2

We can fill two arrays: headProduct and tailProduct. Each headProduct[i] == product of A[0..i-1], tailProduct[i] ==[i+1..A.lenght-1]. They can be built in O(n) and the result could be gathered in O(n). Memory demand is O(n)

eugene on

4

Create a tree, where the leaf nodes are the initial values in the array. Build the binary tree upwards with parent nodes the value of the PRODUCT of its child nodes. After the tree is built, each leaf node's value is replaced by the product of all the value of the "OTHER" child node on its path to root. The pseudo code is like this given int array[1...n] int level_size = n/2; while(level_size != 1){//build the tree int new_array[1...level_size]; for ( int i=0; i left = array[i*2]; (and also from child to parent) new_array[i] -> right = array[i*2+1] new_array[i] = new_array[i] -> right* new_array[i] -> left; (take the product) } array= new_array; level_size /=2; } for(int i=0; iparent; if( parent->left == node){//find the other node under the parent brother = parent->right; } else{ brother = parent->left; } p *= brother; node = parent; } return p; }

Dr Zhang on

1

btw, it's O(n*logn)

Dr Zhang on

3

To husb: Your answer will work, but it's O(n^2) solution. Can you do better?

Interview Candidate on

1

The answer I post above this uses division. Oops. Here is an answer without division static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i 0) { temp -= iArr[i]; newVal++; } iArr[i] = newVal; } }

Marc on

2

Here are my 2 cents to do this in memory without creating temporary arrays. The simple solution , if division was allowed, was multiple all the elements of the array i.e. tolal = A[0]*A[1]]*....*A[n-1] now take a loop of array and update element i with A[i] = toal/A[i] Since division is not allowed we have to simulate it. If we say X*Y = Z, it means if X is added Y times it is equal to Z e.g. 2*3 = 6, which also means 2+2+2 = 6. This can be used in reverse to find how mach times X is added to get Z. Here is my C solution, which take pointer to array head A[0] and size of array as input void ArrayMult(int *A, int size) { int total= 1; for(int i=0; i< size; ++i) total *= A[i]; for(int i=0; i< size; ++i) { int temp = total; int cnt = 0; while(temp) { temp -=A[i]; cnt++; } A[i] = cnt; } } Speed in O(n) and space is O(1)

narya on

0

#include using namespace std; int main() { int y=1,a[23],i,k,s,t,b[76]; cout >s; for(i=0;i>a[i]; for(i=0;i

C ++ on

0

#include using namespace std; int main() { int y=1,a[23],i,k,s,t,b[76]; cout >s; for(i=0;i>a[i]; for(i=0;i

Basics on

0

let arr = [1,2,3,4,5] arr = arr.map((el,i)=>{ return arr.slice(0,i).concat(arr.slice(i+1)).reduce((a,b)=>a*b) }) console.log(arr)

aman khan on

0

traverse once and store all the product of element . For(0 to n-1) A[i]= products*pow(a[i],-1);

Anonymous on

0

Do we know all of the values in the list beforehand? If so I can solve it in 1 pass. Without using any arrays. 1) Compute the product of all values 2) Pick a prime N larger than that product 3) For each cell, multiply the product by the modular multiplicative inverse of the cell value x over N product / x == product * x^-1 mod N == prod * x^(N-2) mod N Example: if the numbers were 1 to 6, compute product of 720, pick N=727. For the cell with 6 in it: 720/6 == 720*6^725 mod 727 == 120 1 pass, no arrays, it's super efficient!!!! As long as you don't think too much about step 2, or step 3.

Seth on

0

Sorry, that last one didn't paste properly static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i 0) { temp -= iArr[i]; newVal++; } iArr[i] = newVal; } }

Marc on

0

p = 1 g = 1 for x in nums: g = g* x + p p = p + x return g

kanwar Malik on

0

Way easy with a simple negative exponent var arr = [2,3,4,5] var prod = arr.reduce((a,b,arr)=>a*b) arr.map((x)=>Math.pow(x,-1)*prod) console.log(arr) //[60,40,30,24]

Christopher R. on

0

I don't know if this is correct. But i think it is. I have done it with python def multiply(numbers,n): total = 1 for x in numbers: if x != n: total *= x return total a = [10, 3, 5, 6, 2] n = 4 prod = [] for i in a: re = multiply(a,i) prod.append(re)

Jyoti on

0

- create a binary tree with the values of array as leaf node - each parent is the product of its children - once the tree is formed, for each value/leaf traverse the tree to the top, each time multiplying the sibling -if tree construction time is ignored, this will take logn time for each calculation and nlogn time for all elements

Maria W on

0

int[] array = new int[]{2,3,4,5}; int m = 1; int m2 = 1; int[] array1 = new int[array.length]; int[] array2 = new int[array.length]; for (int i = 0, j = array.length - 1; i < array.length; i++, j--) { m *= array[i]; array1[i] = m; m2 *= array[j]; array2[j] = m2; } for (int i = 0; i < array.length; i++) { if (i == 0) { System.out.println(array[i] + " " + m2 / array[i] + " " + array2[i + 1]); } else if (i == array.length - 1) { System.out.println(array[i] + " " + m2 / array[i] + " " + array1[i - 1]); } else { System.out.println(array[i] + " " + m2 / array[i] + " " + array1[i - 1] * array2[i + 1]); } }

Andriy on

0

Of course, if allow more temp arrays it can be done in one iteration int[] array = new int[]{2, 3, 4, 6}; int m = 1; int m2 = 1; int[] array1 = new int[array.length]; int[] array2 = new int[array.length]; int[] array3 = new int[array.length]; int middle = array.length / 2; for (int i = 0, j = array.length - 1; i = middle) { if (i + 1 != array.length) { array3[i] = array1[i - 1] * array2[i + 1]; } else { array3[i] = array1[i - 1]; } if (j - 1 >= 0) { array3[j] = array1[j - 1] * array2[j + 1]; } else { array3[j] = array2[j + 1]; } } } for (int i = 0; i < array.length; i++) { System.out.println(array3[i] + "===" + m2 / array[i]); }

Andriy on

1

it looks to me can be done in order n time given the following relation: product[n] = product[n-1]*array[n-1]/array[n] for example we have array 2 3 4 5 6 product[0]=3*4*5*6 product[1]=2*4*5*6 array[0] = 2; array[1]=3 product[1]=product[0]*array[0]/array[1]

dadao on

0

Not commentary

Anonymous on

0

nt a[N] = {1, 2, 3, 4}; int products_below[N]; int products_above[N]; int p=1; int p1=1; for (int i=0;i

AT on

0

def solve(arr,n): product_arr=[1]*n product=1 for i in xrange(n): product_arr[i]*=product product*=arr[i] product=1 for i in xrange(n-1,-1,-1): product_arr[i]*=product product*=arr[i] return product_arr

Ravi Shankar on

0

{{{ If A = {a0, a1, a2, ... an} Construct two arrays called left_p left product and right_p right product: left_p = {1, a0, a0 * a1, a0 * a1 * a2, .... , a0 * a1 * a2 ... * an-1} right_p = {a1*a2*...*an, ....... an-2 * an-1 * an , an-1 * an, an , 1} prod_p[i] = left_p[i] * right_p[i]; }}}

Sravan on

0

O(N) Solution!!! static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i < iArr.Length; i++) { total *= iArr[i]; } for (int i = 0; i < iArr.Length; i++) { iArr[i] = (int)(total * (1 / (double)iArr[i])); } }

Marc on

0

Need help in writing Scala Program for multiplication of 2 elements of array and last element should not exceed 1000. Input Array:(1,3) Output: Array(1,3,3,9,27,243...)

Anonymous on

1

Ah yes.. I was. The question is PRODUCT, not sum. That will teach me to read the question too fast ;)

Bill on

2

Am I missing something? It can't be this easy: given array[0..n] int total = 0; for(int i=0; i<=n; i++) { total += array[i]; } for(int i=0; i<=n; i++) { array[i] = total-array[i]; }

Bill on

3

Given array A[1..n] create array B[1..n]= {1} // all elements =1 ; for (i=1; ij) B[i] *=A[j]; } } A=B;

husb on

7

Create a tree, where the leaf nodes are the initial values in the array.

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.