Multiply Other elements of Array

Interview Question :

Given an array A[], multiply all other elements except the current element and produce the other array O[].

Given Array A={5,2,3,6}

Output Array O = {36,90,6030}

The first element of the output array is 2*3*6 leaving 5

same way second element of output array is 5*3*6 leaving 2.

When you solve the problem keep in the mind that the solution should be time and memory efficient.

Solution :

Alright, When you see the problem, nothing comes out from your mind but simple double for loop. Let's implement using double for loop.

public long[] multiplyElements(int[] a){

//declare and initialize output array elements to 1

long[] o = new long[a.lenght];

for(int i=0;i<a.length;i++){

o[i]=1;

}//end init foor



for(int i=0;i<a.length;i++){

for(int j=0;j<a.lenght;i++){

  if(i==j) continue;

  o[i]* = a[j];

} //ends inner for

} // ends outer for

return o;

}

If you notice this operation takes two for loop means n^2 time to solve the problem. Do you think to avoid n^2 time to solve this problem ?

think...... think.....

Oh yes where is a way to go other way around to solve same problem.

simple logic : multiply all the elements in array first and loop through elements and divide the total by current element which will give the same output as we needed and time complexity will be n+n as there will be two loop 1) for multiplied elements and another for dividing total

so if we consider to calculate for 1000 elements

time taken by double for loop will be n^2 that is =>1000000 compare to later solution which takes n+n=>2n==>2000. Isn't that wonderful ?

Better Solution :

public long[] multiplyElements(int[] a){

long[] o = new long[a.lenght];

long total = 1;

for(int i=0;i<a.length;i++){

  total*=a[i];

}//end init foor



for(int i=0;i<a.length;i++){

  o[i] = total/a[i];

} // ends for

return o;

}