Multiplication of All Element in Array[N] except Array[i] without Divide Operation

Question:

• There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

It is from Google and Microsoft interview Question List. If you want to be hired, see the code. If we use divide operator (/), it's easy to solve in O(n). Multiply of all elements once, and divide into the value of A[i]. And we can implement division function without divide operator, but it may be not way to go. 

Here is a solution. Just define two variable, left and right to store multiplication results of left of A[i] and right of A[i]. We need just one loop of n and hence it's in O(n).

public static void main(String args[]) {
int input[] = {1, 2, 3, 4, 5};
int ret[] = {1,1,1,1,1};
int n = input.length, left=1, right=1;

for(int i=0; i <n; i++) {
ret[i] = ret[i]*left;
ret[n-1-i] = ret[n-1-i]*right;
left *= input[i];
right *= input[n-i-1];
}

for (int i =0; i<n; i++)
System.out.print(ret[i] +"\t");
}

Posted in C, Google Interview Question, Java, MS interview Question, Programming